社区讨论
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 条回复,欢迎继续交流。
正在加载回复...