12182 题解-草地排水

code001

作为一个网络流的题目
这个题目严重缺失属于网络流的威风……
广搜其实应该也可以……
emmm关键是添柴的数据太水了
话不多说放代码

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<cstring>
   
4. int n,m,mi,i,l,r,x,y,z,c[505][505],f[505][505],q[505],flag;
   
5. struct note{int p;int d;}a[20000];
   
6. int main()
   
7. {
   
8.     scanf("%d %d",&n,&m);
   
9.     for(i=1;i<=n;i++)
   
10.     {
    
11.         scanf("%d %d %d",&x,&y,&z);
    
12.         c[x][y]=c[x][y]+z;
    
13.     }
    
14.     flag=1;
    
15.     while(flag!=0)
    
16.     {
    
17.         flag=0;
    
18.         for(i=1;i<=m;i++)
    
19.                         q[i]=1;
    
20.         l=0;
    
21.                 r=1;
    
22.         a[1].p=0;
    
23.         a[1].d=1;
    
24.         while(l<r)
    
25.         {
    
26.             l++;
    
27.             x=a[l].d;
    
28.             for(i=1;i<=m;i++)
    
29.                         {
    
30.                                 if(q[i]&&(c[x][i]>f[x][i]||f[i][x]>0))
    
31.                                 {
    
32.                                         q[i]=0;
    
33.                                         r++;
    
34.                                         a[r].d=i;
    
35.                                         a[r].p=l;
    
36.                                         if(i==m)
    
37.                                         {
    
38.                                                 flag=1;
    
39.                                                 break;
    
40.                                         }
    
41.                                 }
    
42.                         }
    
43.             if(flag==1)
    
44.                                 break;
    
45.         }
    
46.         if (flag==0)
    
47.                         break;
    
48.         mi=999999999;
    
49.         i=r;
    
50.         while (a[i].p!=0)
    
51.         {
    
52.             x=a[i].d;
    
53.             y=a[a[i].p].d;
    
54.             if(c[y][x]>f[y][x]&&c[y][x]-f[y][x]<mi)
    
55.                                 mi=c[y][x]-f[y][x];
    
56.             if(f[x][y]>0&&f[x][y]<mi)
    
57.                                 mi=f[x][y];
    
58.             i=a[i].p;
    
59.         }
    
60.         i=r;
    
61.         while(a[i].p!=0)
    
62.         {
    
63.             x=a[i].d;
    
64.             y=a[a[i].p].d;
    
65.             if(c[y][x]>f[y][x])
    
66.                                 f[y][x]=f[y][x]+mi;
    
67.             if(f[x][y]>0)
    
68.                                 f[x][y]=f[x][y]-mi;
    
69.             i=a[i].p;
    
70.         }
    
71.     }
    
72.     int ans=0;
    
73.     for(i=1;i<=n;i++)
    
74.                 ans=ans+f[1][i];
    
75.     printf("%d",ans);
    
76.     return 0;
    
77. }
    

复制代码

Forinser

是啊
现在是各种模式做
一个A+B都可以用珂朵莉树做，各种神仙代码QAQ

code001

Forinser 发表于 2019-1-29 09:43
是啊
现在是各种模式做
一个A+B都可以用珂朵莉树做，各种神仙代码QAQ

添柴的数据是真的水，都不知道怎么回事

lyt0707

是的，lca用dfs都能水过