[网络流24题] 火星探险问题 (费用流)

和深海机器人那道题不同，这道题要求的是每个点只能被选一次

所以我们把每个点拆成两个，一个入点一个出点，入点出点连一条流量为$1$，费用为$a_{i}$的边

而同一个位置还可能被很多机器人通过，但这些机器人得不到这个点的石头，那么入点出点连一条流量为$inf$，费用为$0$的边

机器人还能往右走或者往下走，每个点的出点向右面和下面的入点连流量为$inf$，费用为$0$的边

由于必须从$(1,1)$出发，$(n,m)$结束，源点和汇点分别连流量为机器人数量，费用为$0$的边

然后跑最大费用最大流即可

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define L1 40
  5 #define N1 3010
  6 #define M1 25010
  7 #define ll long long
  8 #define dd double
  9 #define inf 0x3f3f3f3f
 10 using namespace std;
 11 
 12 int gint()
 13 {
 14     int ret=0,fh=1;char c=getchar();
 15     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
 16     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
 17     return ret*fh;
 18 }
 19 struct Edge{
 20 int head[N1],to[M1<<1],nxt[M1<<1],flow[M1<<1],cost[M1<<1],cte;
 21 void ae(int u,int v,int F,int C)
 22 {
 23     cte++; to[cte]=v; flow[cte]=F; cost[cte]=C;
 24     nxt[cte]=head[u]; head[u]=cte;
 25 }
 26 }e,E;
 27 int K,n,m,nm,S,T;
 28 int a[N1],que[M1],hd,tl,cost[N1],flow[N1],use[N1],id[N1];
 29 int spfa()
 30 {
 31     int x,j,v;
 32     memset(cost,-1,sizeof(cost)); memset(flow,0,sizeof(flow)); 
 33     hd=1,tl=0; que[++tl]=S; cost[S]=0; flow[S]=inf; use[S]=1;
 34     while(hd<=tl)
 35     {
 36         x=que[hd++];
 37         for(j=e.head[x];j;j=e.nxt[j])
 38         {
 39             v=e.to[j]; 
 40             if( cost[v]<cost[x]+e.cost[j] && e.flow[j]>0 )
 41             {
 42                 cost[v]=cost[x]+e.cost[j]; id[v]=j; 
 43                 flow[v]=min(flow[x],e.flow[j]);
 44                 if(!use[v]) que[++tl]=v, use[v]=1;
 45             }
 46         }
 47         use[x]=0;
 48     }
 49     return cost[T]!=-1;
 50 }
 51 int stk[N1],tp;
 52 void dfs(int x)
 53 {
 54     int j,v;
 55     if(x==S) return;
 56     if(x!=T&&x<=nm) stk[++tp]=x;
 57     for(j=e.head[x];j;j=e.nxt[j])
 58     {
 59         v=e.to[j];
 60         if(x>nm){
 61             if( e.flow[j]>0 && v<=nm && v<=x-nm ) 
 62             { e.flow[j]--; dfs(v); break; }
 63         }else{
 64             if( e.flow[j]>0 && v>nm && v<x+nm ) 
 65             { e.flow[j]--; dfs(v); break; }
 66         }
 67     }
 68 }
 69 int EK()
 70 {
 71     int x,fl,tcost=0,i,j;
 72     while(spfa())
 73     {
 74         fl=flow[T]; tcost+=fl*cost[T]; 
 75         for(x=T;x!=S;x=e.to[id[x]^1])
 76         {
 77             e.flow[id[x]]-=fl;
 78             e.flow[id[x]^1]+=fl;
 79         }
 80     }
 81     for(i=1;i<=n;i++) 
 82     {
 83         dfs(2*nm);
 84         for(j=tp;j>1;j--)
 85         {
 86             if(stk[j-1]==stk[j]+m) printf("%d 0
",i);
 87             if(stk[j-1]==stk[j]+1) printf("%d 1
",i);
 88         }
 89         tp=0;
 90     }
 91     return tcost;
 92 }
 93 
 94 int mp[L1][L1];
 95 int check(int x,int y){
 96     if(x<1||y<1||x>n||y>m||mp[x][y]==1) return 0; return 1;
 97 }
 98 int idd(int x,int y){ return (x-1)*m+y; }
 99 
100 int main()
101 {
102     int i,j,da,db; 
103     scanf("%d%d%d",&K,&m,&n);
104     nm=n*m; S=0; T=2*nm+1; e.cte=1; 
105     for(i=1;i<=n;i++) for(j=1;j<=m;j++) mp[i][j]=gint();
106     for(i=1;i<=n;i++) for(j=1;j<=m;j++)
107     {
108         if(!check(i,j)) continue;
109         da=idd(i,j); 
110         if(mp[i][j]) e.ae(da,da+nm,1,1), e.ae(da+nm,da,0,-1);
111         e.ae(da,da+nm,inf,0), e.ae(da+nm,da,0,0);
112         if(check(i+1,j))
113         {
114             db=idd(i+1,j);
115             e.ae(da+nm,db,inf,0);
116             e.ae(db,da+nm,0,0);
117         } 
118         if(check(i,j+1))
119         {
120             db=idd(i,j+1);
121             e.ae(da+nm,db,inf,0);
122             e.ae(db,da+nm,0,0);
123         }
124     }
125     e.ae(S,1,K,0); e.ae(1,S,0,0);
126     e.ae(2*nm,T,K,0); e.ae(T,2*nm,0,0);
127     EK();//printf("%d
",);
128     return 0;
129 }