12182

lyt0707

1. #include <cstdio>
   
2. #include <cstring>
   
3. using namespace std;
   
4. int n,m,e[301][301],flag=0,top,s[100009],ans,book[100009];
   
5. void dfs(int u)
   
6. {
   
7.         if(u==n)
   
8.         {
   
9.                 top++;
   
10.                 s[top]=n;
    
11.                 int minx=2147483647;
    
12.                 for(int i=1;i<top;i++)
    
13.                 {
    
14.                         if(e[s[i]][s[i+1]]<minx)
    
15.                         {
    
16.                                 minx=e[s[i]][s[i+1]];
    
17.                         }
    
18.                 }
    
19.                 ans+=minx;
    
20.                 for(int i=1;i<top;i++)
    
21.                 {
    
22.                         e[s[i]][s[i+1]]-=minx;
    
23.                         e[s[i+1]][s[i]]+=minx;
    
24.                 }
    
25.                 flag=1;
    
26.                 return;
    
27.         }
    
28.         if(book[u]==1)
    
29.         {
    
30.                 return;
    
31.         }
    
32.         book[u]=1;
    
33.         top++;
    
34.         s[top]=u;
    
35.        
    
36.         for(int i=1;i<=n;i++)
    
37.         {
    
38.                 if(e[u][i]>0)
    
39.                 {
    
40.                         dfs(i);
    
41.                 }
    
42.         }
    
43.         top--;
    
44.         return;
    
45. }
    
46. int main()
    
47. {
    
48.     scanf("%d%d",&m,&n);
    
49.     for(int i=1;i<=m;i++)
    
50.     {
    
51.         int a,b,c;
    
52.         scanf("%d%d%d",&a,&b,&c);
    
53.         e[a][b]+=c;
    
54.     }
    
55.     while(1>0)
    
56.     {
    
57.             memset(book,0,sizeof(book));
    
58.         flag=0;
    
59.         top=0;
    
60.                 dfs(1);
    
61.         if(flag==0)
    
62.         {
    
63.             break;
    
64.         }
    
65.     }
    
66.     printf("%d",ans);
    
67.     return 0;
    
68. }

复制代码

睿利之刃

大佬可以看可以六六六啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿绿2222222来来来了2来来