社区讨论

E? 刚学网络流,求助

P2598[ZJOI2009] 狼和羊的故事参与者 5已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@mi86m6er
此快照首次捕获于
2025/11/21 09:28
4 个月前
此快照最后确认于
2025/11/21 09:28
4 个月前
查看原帖
E?
WA了5个点
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define E puts("E?")
#define id(x,y) ((x-1)*n+y)
#define min(a,b) (a<b?a:b)
using namespace std;
const int N=105,M=1000005,inf=((1<<30)-1)<<1;
struct Edge{
	int nxt,to,flow,ops;
	};
Edge edge[M<<1];
int pre[N*N],cnt;
void add_for(int u,int v,int w){
	edge[++cnt].nxt=pre[u];
	edge[cnt].to=v;
	edge[cnt].flow=w;
	edge[cnt].ops=(cnt&1)?cnt+1:cnt-1;
	pre[u]=cnt;
	}
void add(int u,int v,int w){
	add_for(u,v,w);
	add_for(v,u,0);
	}	
int n,m,st,ed,ans;
int dep[N*N];
queue<int>que;
bool BFS(){
	while(!que.empty()){
		que.pop();
		}
	memset(dep,0,sizeof(dep));
	que.push(st);
	dep[st]=1;
	while(!que.empty()){
		int u=que.front();
		que.pop();
		for(int i=pre[u];i>0;i=edge[i].nxt){
			int v=edge[i].to;
			if(!dep[v]&&edge[i].flow){
				dep[v]=dep[u]+1;
				que.push(v);
				}
			}
		}
	return dep[ed]==0?0:1;	
	}
int DFS(int u,int dis){
	if(u==ed){
		return dis;
		}
	int now=dis;
	for(int i=pre[u];i>0;i=edge[i].nxt){
		int v=edge[i].to;
		if(dep[v]==dep[u]+1&&edge[i].flow&&now){
			int flow=DFS(v,min(now,edge[i].flow));
			if(flow){
				edge[i].flow-=flow;
				int j=edge[i].ops;
				edge[j].flow+=flow;
				now-=flow;
				}
			}
		}
	return dis-now;	
	}	
int Dinic(){
	int ans=0;
	while(BFS()){	
		int flow;
		while(flow=DFS(st,inf)){
			ans+=flow;
			}
		}
	return ans;	
	}	
int a[N][N];
int fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	st=0;
	ed=n*m+1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){	
			cin>>a[i][j];
			if(a[i][j]==1){
				add(st,id(i,j),inf);
				}
			if(a[i][j]==2){
				add(id(i,j),ed,inf);
				}	
			}
		}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<4;k++){
				int x=i+fx[k][0],y=j+fx[k][1];
				if(x<1||x>n||y<1||y>m){	
					continue;
					}
				add(id(i,j),id(x,y),1);	
				}
			}
		}
	ans=Dinic();
	cout<<ans;
	return 0;
	}

回复

9 条回复,欢迎继续交流。

正在加载回复...