网络流一条边都不能多连？没道理呀？
不过单看这题的确是个sb题……
#include<cstdio> #include<algorithm> #include<cstring> #include<cctype> #include<cstdlib> #include<queue> #define maxn 100 #define maxm 100000 #define lim n*m #define F(i,j) ((i-1)*m+j) #define T(i,j) (F(i,j)+lim) using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } struct Edge{ int from,next,to,val,dis,flow; }edge[maxm]; int head[maxn*maxn],num; inline void addedge(int from,int to,int val,int dis){ edge[++num]=(Edge){from,head[from],to,val,dis,0}; head[from]=num; } inline void add(int from,int to,int val,int dis){ addedge(from,to,val,dis); addedge(to,from,0,-dis); } inline int count(int i){ return i&1?i+1:i-1; } int dis[maxn*maxn]; int flow[maxn*maxn]; int pre[maxn*maxn]; bool vis[maxn*maxn]; int Start,End; int n,m; int spfa(){ memset(dis,-127/3,sizeof(dis)); dis[Start]=0; flow[Start]=0x7fffffff; queue<int>q; q.push(Start); while(!q.empty()){ int from=q.front(); q.pop(); vis[from]=0; for(int i=head[from];i;i=edge[i].next){ int to=edge[i].to; if(edge[i].val<=edge[i].flow||dis[to]>=dis[from]+edge[i].dis) continue; dis[to]=dis[from]+edge[i].dis; pre[to]=i; flow[to]=min(flow[from],edge[i].val-edge[i].flow); if(vis[to]) continue; vis[to]=1; q.push(to); } } int now=End; while(now!=Start){ int ret=pre[now]; edge[ret].flow+=flow[End]; edge[count(ret)].flow-=flow[End]; now=edge[ret].from; } return dis[End]; } struct Node{ int x,y; }; Node calc(int ret){ Node ans; ans.x=(ret-1)/m+1; ans.y=ret-(ans.x-1)*m; return ans; } Node q[maxn*maxn];int tot; void dfs(int x,int y,int now){ if(now==End) return; for(int i=head[now];i;i=edge[i].next){ int to=edge[i].to; if(edge[i].flow==0) continue; edge[i].flow--; edge[i].val--; if(to<=lim) q[++tot]=calc(to); dfs(q[tot].x,q[tot].y,to); return; } } bool ext[maxn][maxn]; int main(){ int e=read(); m=read();n=read(); Start=1; End=n*m*2; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ int x=read(); if(i!=1&&ext[i-1][j]==0) add(T(i-1,j),F(i,j),0x7fffffff,0); if(j!=1&&ext[i][j-1]==0) add(T(i,j-1),F(i,j),0x7fffffff,0); if(x==1){ ext[i][j]=1; continue; } add(F(i,j),T(i,j),1,x==2?1:0); add(F(i,j),T(i,j),0x7fffffff,0); } int cnt=0; while(1){ int now=spfa(); if(now<0) break; cnt++; if(cnt>e) break; tot=0; dfs(1,1,1); q[0]=(Node){1,1}; for(int j=1;j<=tot;++j){ Node a=q[j-1],b=q[j]; if(a.x==b.x) printf("%d %d ",cnt,1); else printf("%d %d ",cnt,0); } } return 0; }