暑假集训Day24 E (拆点建边网络流)

题目链接在这里:20182019-acmicpc-pacific-northwest-regional-contest-div-1-en.pdf (codeforces.com)

题目大意是给了一个图,要你用最小的代价把小偷封住不让他跑出去,从题意来看是一道很明显的最小割的题目。

对于这种非典型的最小割常见思路是拆点。将每个点拆成入点和出点,入点和出点之间连一条边,如果当前为字母,该边的权值即为字母对应的权值,否则为无穷大(表示此处流量没有限制)。然后每个点的出点和相邻点的入点连一条边,权值为无穷大,表示此处流量没有限制。最后跑网络流最小割。

关于网络流最大流最小割,可以看这个视频学习:

有几个要注意的,一个是建边的时候要同时建两条边,反边的权值为0.另一个是tot的初值要为1,因为这样每个边^1才是它的反边。

 1 #include "bits/stdc++.h"
 2 #define fi first
 3 #define se second
 4 using namespace std;
 5 const int MAX=1e5+5;
 6 const int oo=1e9;
 7 char s[35][35];
 8 int n,m,c,a[35],ss,tt;
 9 int tot,head[MAX],adj[MAX],wei[MAX],nxt[MAX];
10 int deep[MAX];
11 int dx[]={1,0,-1,0};
12 int dy[]={0,1,0,-1};
13 void addedge(int u,int v,int w){
14     tot++;
15     adj[tot]=v;
16     wei[tot]=w;
17     nxt[tot]=head[u];
18     head[u]=tot;
19     tot++;
20     adj[tot]=u;
21     wei[tot]=0;
22     nxt[tot]=head[v];
23     head[v]=tot;
24 }
25 inline int getid(int x,int y,int z){
26     if (x<1 || x>n || y<1 || y>m) return MAX-5;
27     return 2*((x-1)*m+y)+z;
28 }
29 bool bfs(){
30     int i,j,zt;
31     queue <int> q;
32     while (!q.empty()) q.pop();
33     q.push(ss);
34     memset(deep,-1,sizeof(deep));
35     deep[ss]=0;
36     while (!q.empty()){
37         zt=q.front(); q.pop();
38         for (i=head[zt];i;i=nxt[i])
39             if (deep[adj[i]]==-1 && wei[i]>0){
40                 deep[adj[i]]=deep[zt]+1;
41                 q.push(adj[i]);
42             }
43     }
44     return (deep[tt]!=-1);
45 }
46 int dfs(int x,int v){
47     if (x==tt) return v;
48     int i,j,now=0,zt;
49     for (i=head[x];i && now<v;i=nxt[i])
50         if (deep[adj[i]]==deep[x]+1 && wei[i]>0){
51             zt=dfs(adj[i],min(wei[i],v-now));
52             now+=zt;
53             wei[i]-=zt;
54             wei[i^1]+=zt;
55         }
56     if (now==0) deep[x]=-2;
57     return now;
58 }
59 int main(){
60     freopen ("e.in","r",stdin);
61     freopen ("e.out","w",stdout);
62     int i,j,k,zt,ans=0;
63     scanf("%d%d%d",&m,&n,&c);
64     for (i=1;i<=n;i++)
65         scanf("%s",s[i]+1);
66     for (i=1;i<=c;i++)
67         scanf("%d",a+i);
68     tot=1;tt=MAX-5;
69     memset(head,0,sizeof(head));
70     for (i=1;i<=n;i++)
71         for (j=1;j<=m;j++){
72             if (s[i][j]=='B') ss=getid(i,j,1);
73             if (s[i][j]=='.')
74                 addedge(getid(i,j,0),getid(i,j,1),oo);
75             if (s[i][j]>='a' && s[i][j]<='z')
76                 addedge(getid(i,j,0),getid(i,j,1),a[s[i][j]-'a'+1]);
77             for (k=0;k<4;k++)
78                 addedge(getid(i,j,1),getid(i+dx[k],j+dy[k],0),oo);
79         }
80     ans=0;
81     while (bfs()){
82         while (zt=dfs(ss,oo),zt){
83             ans+=zt;
84             if (ans>=1e9) goto away;
85         }
86     }
87     away:printf("%d",(ans<1e9?ans:-1));
88     return 0;
89 }
未来是什么样,未来会发生什么,谁也不知道。 但是我知道, 起码从今天开始努力, 肯定比从明天开始努力, 要快一天实现梦想。 千里之行,始于足下! ——《那年那兔那些事儿》
原文地址:https://www.cnblogs.com/keximeiruguo/p/15185899.html