【LOJ6225&网络流24题】火星探险问题（费用流）

题意：

思路：

【问题分析】

最大费用最大流问题。

【建模方法】

把网格中每个位置拆分成网络中两个节点<i.a>,<i.b>，建立附加源S汇T。

1、对于每个顶点i，j为i东边或南边相邻的一个节点，连接节点<i.b>与节点<j.a>一条容量为无穷大，费用为0的有向边。

2、从每个石块顶点<i.a>到<i.b>连接一条容量为1，费用为1的有向边。

3、从每个非障碍顶点<i.a>到<i.b>连接一条容量为无穷大，费用为0的有向边。

4、从S到登陆舱位置<(1,1),a>连接一条容量为探测车数，费用为0的有向边。

5、从传送器位置<(P,Q),a>到T连接一条容量为探测车数，费用为0的有向边。

求最大费用最大流，最大费用流值就是最多的岩石标本的数量。所有满流边构成多条满流路径，每条从S到T的路径就是一个探测车的路径。

【建模分析】

这个问题可以看做是出发点和目的地唯一的网络运输问题。每个石块点的价值只能计算一次，所以容量限制要设为1，“多个探测车可以在同一时间占据同一位置”，非障碍点内部要有一条容量为无穷大的

边。直接求费用流即可。

输出方案不能直接记增广路上的点，要重新dfs一遍

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef long double ld;
  7 typedef pair<int,int> PII;
  8 typedef pair<ll,ll> Pll;
  9 typedef vector<int> VI;
 10 typedef vector<PII> VII;
 11 typedef pair<ll,ll>P;
 12 #define N  500000
 13 #define M  1000000
 14 #define INF 1e9
 15 #define fi first
 16 #define se second
 17 #define MP make_pair
 18 #define pb push_back
 19 #define pi acos(-1)
 20 #define mem(a,b) memset(a,b,sizeof(a))
 21 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 22 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 23 #define lowbit(x) x&(-x)
 24 #define Rand (rand()*(1<<16)+rand())
 25 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 26 #define ls p<<1
 27 #define rs p<<1|1
 28 
 29 const ll MOD=1e9+7,inv2=(MOD+1)/2;
 30       double eps=1e-6;
 31       int dx[4]={-1,1,0,0};
 32       int dy[4]={0,0,-1,1};
 33 
 34 struct node
 35 {
 36     int x,y;
 37 }p[N];
 38 
 39 VI c;
 40 
 41 int head[N],vet[N],nxt[N],len1[N],len2[N],dis[N],inq[N],q[N],pre[N][2],num[50][50][2],a[50][50],f[N],
 42     s,S,T,tot,ans1,ans2,n,m;
 43 
 44 int read()
 45 {
 46    int v=0,f=1;
 47    char c=getchar();
 48    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 49    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 50    return v*f;
 51 }
 52 
 53 void add(int a,int b,int c,int d)
 54 {
 55     nxt[++tot]=head[a];
 56     vet[tot]=b;
 57     len1[tot]=c;
 58     len2[tot]=d;
 59     head[a]=tot;
 60 
 61     nxt[++tot]=head[b];
 62     vet[tot]=a;
 63     len1[tot]=0;
 64     len2[tot]=-d;
 65     head[b]=tot;
 66 }
 67 
 68 int spfa()
 69 {
 70     rep(i,1,s)
 71     {
 72         dis[i]=-INF;
 73         inq[i]=0;
 74     }
 75     int t=0,w=1;
 76     q[1]=S; dis[S]=0; inq[S]=1;
 77     while(t<w)
 78     {
 79         t++; int u=q[t%(s+5)]; inq[u]=0;
 80         int e=head[u];
 81         while(e)
 82         {
 83             int v=vet[e];
 84             if(len1[e]&&dis[u]+len2[e]>dis[v])
 85             {
 86                 dis[v]=dis[u]+len2[e];
 87                 pre[v][0]=u;
 88                 pre[v][1]=e;
 89                 if(!inq[v])
 90                 {
 91                     w++; q[w%(s+5)]=v; inq[v]=1;
 92                 }
 93             }
 94             e=nxt[e];
 95         }
 96     }
 97     if(dis[T]==-INF) return 0;
 98     return 1;
 99 }
100 
101 void dfs(int x,int y)
102 {
103     int u=num[x][y][1];
104     int e=head[u];
105     while(e)
106     {
107         if(f[e]>=len1[e^1])
108         {
109             e=nxt[e];
110             continue;
111         }
112 
113         int v=vet[e];
114         if(v==num[x+1][y][0])
115         {
116             f[e]++; c.pb(0);
117             dfs(x+1,y);
118             return;
119         }
120          else if(v==num[x][y+1][0])
121          {
122              f[e]++; c.pb(1);
123              dfs(x,y+1);
124              return;
125          }
126         e=nxt[e];
127     }
128 }
129 
130 void mcf()
131 {
132     int k=T,t=INF;
133     while(k!=S)
134     {
135         int e=pre[k][1];
136         t=min(t,len1[e]);
137         k=pre[k][0];
138     }
139     ans1+=t;
140     k=T;
141     while(k!=S)
142     {
143         int e=pre[k][1];
144         len1[e]-=t;
145         len1[e^1]+=t;
146         ans2+=t*len2[e];
147         k=pre[k][0];
148     }
149 }
150 
151 int main()
152 {
153     //freopen("1.in","r",stdin);
154     //freopen("1.out","w",stdout);
155     int car=read();
156     n=read(),m=read();
157     swap(n,m);
158     rep(i,1,n)
159      rep(j,1,m) a[i][j]=read();
160     s=0;
161     rep(i,1,n)
162      rep(j,1,m)
163       rep(k,0,1)
164       {
165           num[i][j][k]=++s;
166           p[s].x=i; p[s].y=j;
167       }
168 
169     S=++s,T=++s;
170     p[S].x=p[S].y=1;
171     p[T].x=n; p[T].y=m;
172     rep(i,1,s) head[i]=0;
173     tot=1;
174     rep(i,1,n)
175      rep(j,1,m)
176      {
177          if(a[i][j]==1) continue;
178          add(num[i][j][0],num[i][j][1],INF,0);
179          if(a[i][j]==2) add(num[i][j][0],num[i][j][1],1,1);
180      }
181     rep(i,1,n)
182      rep(j,1,m)
183      {
184          if(a[i][j]==1) continue;
185          if(i+1<=n&&a[i+1][j]!=1) add(num[i][j][1],num[i+1][j][0],INF,0);
186          if(j+1<=m&&a[i][j+1]!=1) add(num[i][j][1],num[i][j+1][0],INF,0);
187      }
188     add(S,num[1][1][0],car,0);
189     add(num[n][m][1],T,car,0);
190     ans1=ans2=0;
191     while(spfa()) mcf();
192     rep(i,1,ans1)
193     {
194         c.clear();
195         dfs(1,1);
196         for(int j=0;j<c.size();j++) printf("%d %d
",i,c[j]);
197     }
198     return 0;
199 
200 }