Time Limit: 1 Sec Memory Limit: 128 MB
Description
.jpg)
.jpg)
Input
第1行输入N，之后N行每行描述一条水管，前两个英文字母表示水管的两端（大小写字母是不一样的），后一个整数表示水管的流量，流量不会超过1000.
Output
一个整数，表示总流量．
Sample Input
5
A B 3
B C 3
C D 5
D Z 4
B Z 6
Sample Output
3
HINT
Source
Silver
Solution
网络流最大流模板题。（这题不用long long，我写long long就是为了写个模板）
下面的代码中写了当前弧优化。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=55,M=1500; int m,tot,Next[M],head[N],tree[M],n,S,T,cur[N],h[N],x[N*3]; long long val[M],ans; char s1[1],s2[1]; void add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } bool bfs() { int t=0,w=1; memset(h,-1,sizeof(h)); x[1]=S;h[1]=0; while (t!=w) { int u=x[++t]; for (int i=head[u];i;i=Next[i]) if (val[i]!=0&&h[tree[i]]==-1) { x[++w]=tree[i]; h[tree[i]]=h[u]+1; } } return h[T]!=-1; } long long dfs(int u,long long low) { if (u==T) return low; long long used=0; for (int i=cur[u];i;i=Next[i]) { int v=tree[i]; if (h[v]==h[u]+1) { long long w=dfs(v,min(val[i],low-used)); val[i]-=w;val[i^1]+=w; used+=w; cur[u]=i; if (used==low) return low; } } if (used==0) h[u]=-1; return used; } void dinic() { while (bfs()) { for (int i=1;i<=n;i++) cur[i]=head[i]; ans+=dfs(S,1LL<<60); } } int main() { scanf("%d",&m); tot=1; for (int i=1;i<=m;i++) { long long d; int x,y; scanf("%s%s%lld",s1,s2,&d); if (s1[0]>='A'&&s1[0]<='Z') x=s1[0]-'A'+1;else x=s1[0]-'a'+27; if (s2[0]>='A'&&s2[0]<='Z') y=s2[0]-'A'+1;else y=s2[0]-'a'+27; add(x,y,d);add(y,x,0); } ans=0;n=55; S=1;T=26; dinic(); printf("%lld\n",ans); return 0; } |
