「BZOJ3396」[Usaco2009 Jan] Total flow 水流
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
题解
直接上网络流模板。。。
似乎有小写字母
|
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 80 81 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define inf 0x7fffffff #define ll long long #define T 26 using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt=1,ans; int head[65],cur[65],h[65],q[65]; struct data{int to,next,v;}e[2005]; void ins(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w; } void insert(int u,int v,int w) { ins(u,v,w);ins(v,u,0); } bool bfs() { int t=0,w=1; memset(h,-1,sizeof(h)); h[1]=0;q[0]=1; while(t!=w) { int now=q[t];t++; for(int i=head[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[w++]=e[i].to; } } return h[T]!=-1; } int dfs(int x,int f) { int w,used=0; if(x==T)return f; for(int i=cur[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=f-used;w=dfs(e[i].to,min(e[i].v,w)); e[i].v-=w;if(e[i].to)cur[x]=i; e[i^1].v+=w;used+=w; if(used==f)return f; } if(!used)h[x]=-1; return used; } void dinic() {while(bfs()){for(int i=1;i<=60;i++)cur[i]=head[i];ans+=dfs(1,inf);}} int main() { n=read(); for(int i=1;i<=n;i++) { char ch[5];int a,b; scanf("%s",ch); if(ch[0]>='A'&&ch[0]<='Z')a=ch[0]-'A'+1; else a=ch[0]-'a'+; scanf("%s",ch); if(ch[0]>='A'&&ch[0]<='Z')b=ch[0]-'A'+1; else b=ch[0]-'a'+27; int x=read(); insert(a,b,x); } dinic(); printf("%d",ans); return 0; } |
Subscribe
计数器 9792970
OI 课件=>
OI 课件=>