网络流44pts求助
查看原帖
网络流44pts求助
602803
_qingshu_楼主2024/8/5 10:53
#include<bits/stdc++.h>
using namespace std;
int n;
char mp[520][520];
struct edge{
	int to,nxt;
	int val,spendf;
}e[5200010];
int tot=1,head[5200010],s,t;
inline void add(int nxt,int to,int val,int spendf){
	e[++tot].to=to;
	e[tot].nxt=head[nxt];
	e[tot].val=val;
	e[tot].spendf=spendf;
	head[nxt]=tot;
	
	e[++tot].to=nxt;
	e[tot].nxt=head[to];
	e[tot].val=0;
	e[tot].spendf=-spendf;
	head[to]=tot;
}
int ans=0,dis[5200010],vis[5200010];
inline bool spfa(){
	for(int i=1;i<=1002;i++){
		dis[i]=INT_MAX;
	}
	queue<int>q;
	q.push(s);
	dis[s]=0;
	vis[s]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].to;
			if(e[i].val&&dis[v]>dis[x]+e[i].spendf){
				dis[v]=dis[x]+e[i].spendf;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				} 
			} 
		}
	}
	return dis[t]!=INT_MAX;
}
inline int dfs(int x,int sum){
	if(x==t)return sum;
	int res=0;
	vis[x]=1;
	for(int i=head[x];i&&sum;i=e[i].nxt){
		int v=e[i].to;
		if(e[i].val&&!vis[v]&&dis[v]==dis[x]+e[i].spendf){
			int k=dfs(v,min(sum,e[i].val));
			e[i].val-=k;
			e[i^1].val+=k;
			sum-=k;
			res+=k; 
			ans+=k*e[i].spendf;
		} 
	}
	vis[x]=0;
	return res;
}
inline void dinic(){
	while(spfa()){
		dfs(s,INT_MAX);
	}
}
int cx[]={1,0,0,-1};
int cy[]={0,1,-1,0};
inline void getans(int id){
	if(id==t)return;
	for(int i=head[id];i;i=e[i].nxt){
		int v=e[i].to;
		if(i%2==0&&e[i^1].val){
			if(id!=s&&v!=t){
				cout<<((id-1)/4+1)<<(id%4==0?4:id%4)<<((v-1)/4+1)<<(v%4==0?4:v%4)<<"\n";
			}
			e[i^1].val--;e[i].val++;getans(v);
			if(id!=s)break;
		}
	}
}
int main(){
	s=1001;t=s+1;
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			cin>>mp[i][j];
			if(mp[i][j]=='1'){
				add(s,(i-1)*4+j,1,0);
			}
			for(int k=0;k<4;k++){
				int x=i+cx[k],y=j+cy[k];
				if(x>=1&&x<=4&&y>=1&&y<=4){
					add((i-1)*4+j,(x-1)*4+y,INT_MAX,1);
				}
			}
		} 
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			cin>>mp[i][j];
			if(mp[i][j]=='1'){
				add((i-1)*4+j,t,1,0);
			}
		} 
	}
	dinic();
	cout<<ans<<"\n";
	getans(s);
}
2024/8/5 10:53
加载中...