题目链接
网络流一条边都不能多连? 没道理呀?
不过单看这题的确是个 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\n",cnt,1);
- else printf("%d %d\n",cnt,0);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2498859.html