[网络流24题] 深海机器人
时间限制：1 s 内存限制：128 MB
标为 (Q,P)。
2 2 2
shinkai.out
42
1<=P,Q<=15 1<=a,b<=10
主要的难点是如何通过一个点却只计算一次价值，事实上处理方法很简单，连两次边，第一条权值为0，流量inf，第二次权值为x，流量为1。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=300; 4 const int maxm=maxn*8; 5 const int inf=0x3fffffff; 6 int a,b,p,q,num[17][17],cnt; 7 int tot=-1,fi[maxn],next[maxm],to[maxm],cost[maxm],flow[maxm]; 8 int ans,s,t,dis[maxn],que[maxn],head,tail,cur[maxn],vis[maxn]; 9 void edge_add(int x,int y,int f,int c){ 10 to[++tot]=y;next[tot]=fi[x];fi[x]=tot;cost[tot]=c;flow[tot]=f; 11 to[++tot]=x;next[tot]=fi[y];fi[y]=tot;cost[tot]=-c;flow[tot]=0; 12 } 13 bool bfs(){ 14 head=tail=1; 15 for(int i=s;i<=t;i++)cur[i]=fi[i],vis[i]=0,dis[i]=-inf; 16 que[++tail]=s;vis[s]=1;dis[s]=0; 17 while(head!=tail){ 18 head++; 19 if(head==290)head=1; 20 int u=que[head]; 21 vis[u]=0; 22 for(int i=fi[u];i+1;i=next[i]){ 23 if(flow[i]&&dis[to[i]]<dis[u]+cost[i]){ 24 dis[to[i]]=dis[u]+cost[i]; 25 if(!vis[to[i]]){ 26 vis[to[i]]=1; 27 tail++; 28 if(tail==290)tail=1; 29 que[tail]=to[i]; 30 } 31 } 32 } 33 } 34 return dis[t]!=-inf; 35 } 36 int dfs(int x,int f){ 37 vis[x]=1; 38 if(x==t)return f; 39 for(int i=cur[x];i+1;i=next[i]){ 40 cur[x]=i; 41 if(!vis[to[i]]&&flow[i]&&dis[to[i]]==dis[x]+cost[i]){ 42 int g=dfs(to[i],min(flow[i],f)); 43 if(g){ 44 ans+=cost[i]*g; 45 flow[i]-=g; 46 flow[i^1]+=g; 47 return g; 48 } 49 } 50 } 51 return 0; 52 } 53 void dinic(){ 54 while(bfs()) 55 while(dfs(s,inf)); 56 printf("%d\n",ans); 57 } 58 int main() 59 { 60 scanf("%d%d",&a,&b); 61 scanf("%d%d",&p,&q); 62 memset(fi,-1,sizeof(fi)); 63 p++;q++; 64 for(int i=1;i<=p;i++) 65 for(int j=1;j<=q;j++) 66 num[i][j]=++cnt; 67 s=0;t=cnt+1; 68 for(int i=1;i<=p;i++){ 69 for(int j=1;j<q;j++){ 70 int x; 71 scanf("%d",&x); 72 edge_add(num[i][j],num[i][j+1],inf,0); 73 edge_add(num[i][j],num[i][j+1],1,x); 74 } 75 } 76 for(int i=1;i<=q;i++){ 77 for(int j=1;j<p;j++){ 78 int x; 79 scanf("%d",&x); 80 edge_add(num[j][i],num[j+1][i],inf,0); 81 edge_add(num[j][i],num[j+1][i],1,x); 82 } 83 } 84 for(int i=1;i<=a;i++){ 85 int k,x,y; 86 scanf("%d%d%d",&k,&x,&y); 87 edge_add(s,num[x+1][y+1],k,0); 88 } 89 for(int i=1;i<=b;i++){ 90 int k,x,y; 91 scanf("%d%d%d",&k,&x,&y); 92 edge_add(num[x+1][y+1],t,k,0); 93 } 94 dinic(); 95 return 0; 96 }
