1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 20014 #define maxm 150015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26     int x=0,f=1;char ch=getchar();27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29     return x*f;30 }31 int  n,m,s,t,maxflow,tot=1,head[maxn],cur[maxn],h[maxn],q[maxn];32 struct edge{int go,next,v;}e[maxm];33 void ins(int x,int y,int z){e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;}34 void insert(int x,int y,int z){ins(x,y,z);ins(y,x,0);}35 bool bfs()36 {37     for(int i=1;i<=150;i++)h[i]=-1;38     int l=0,r=1;q[1]=s;h[s]=0;39     while(l<r)40     {41         int x=q[++l];42         for(int i=head[x];i;i=e[i].next)43          if(e[i].v&&h[e[i].go]==-1)44          {45             h[e[i].go]=h[x]+1;q[++r]=e[i].go;46          }47     }48     return h[t]!=-1;49 }50 int dfs(int x,int f)51 {52     if(x==t) return f;53     int tmp,used=0;54     for(int i=head[x];i;i=e[i].next)55      if(e[i].v&&h[e[i].go]==h[x]+1)56     {57         tmp=dfs(e[i].go,min(e[i].v,f-used));58         e[i].v-=tmp;if(e[i].v)cur[x]=i;59         e[i^1].v+=tmp;used+=tmp;60         if(used==f)return f;       61     }62     if(!used) h[x]=-1;63     return used;64 }65 void dinic()66 {67     maxflow=0;68     while(bfs())69     {70         for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=dfs(s,inf);71     }72 }73 inline int get()74 {75     char ch=‘ ‘;76     while((ch<‘a‘||ch>‘z‘)&&(ch<‘A‘||ch>‘Z‘))ch=getchar();77     return ch;78 }79 int main()80 {81     freopen("input.txt","r",stdin);82     freopen("output.txt","w",stdout);83     n=read();84     for1(i,n)85      {86          int x=get(),y=get(),z=read();87          insert(x,y,z);88      }89     s=(int)‘A‘;t=(int)‘Z‘;90     dinic();91     printf("%d\n",maxflow);92     return 0;93 }