【POJ各种模板汇总】（写在逆风省选前）（不断更新中）

 1 #include<cstring>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 const int maxn=100,inf=1e8;
 6 int d[maxn+50],g[maxn+50][maxn+50],ans=0,n;
 7 bool v[maxn+50];
 8 int main()
 9 {
10     scanf("%d",&n);
11     for(int i=1;i<=n;++i)
12         for(int j=1;j<=n;++j)
13         {
14             scanf("%d",&g[i][j]);
15             if(g[i][j]==0) g[i][j]=inf;
16         }
17     memset(v,0,sizeof(v));
18     for(int i=1;i<=n;++i) d[i]=g[1][i];
19     d[1]=0;
20     v[1]=1;
21     for(int j=2;j<=n;++j)
22     {
23         int m=inf,k=j;
24         for(int i=1;i<=n;++i)
25             if(v[i]==0&&d[i]<m) m=d[i],k=i;
26         ans+=m;
27         v[k]=1;
28         for(int i=1;i<=n;++i)
29             if(v[i]==0&&g[k][i]<d[i]) d[i]=g[k][i];
30     }
31     printf("%d",ans);
32     return 0;
33 }

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 using namespace std;
 6 const int maxn=200,maxm=200,inf=1e8;
 7 struct wjmzbmr
 8 {
 9     int to,flow;
10 }e[maxm*2+50];
11 vector<int> g[maxn+50];
12 int n,m,ans=0,d[maxn+50],dv[maxn+50];
13 int dfs(int k,int flow)
14 {
15     if (k==n) return flow;
16     int s=0;
17     for(int i=0;i<g[k].size();++i)
18     {
19         wjmzbmr t=e[g[k][i]];
20         if(t.flow<=0||d[k]!=d[t.to]+1) continue;
21         int x=dfs(t.to,min(flow-s,t.flow)); 
22         e[g[k][i]].flow-=x;
23         e[g[k][i]^1].flow+=x;
24         s+=x;
25         if(s==flow) return s;
26     }
27     if(d[1]==n+1) return s;
28     --dv[d[k]];
29     if(dv[d[k]]==0) d[1]=n+1;
30     d[k]++;
31     dv[d[k]]++;
32     return s;
33 }
34 int main()
35 {
36     while (scanf("%d %d",&m,&n)!=EOF)
37     {
38         memset(dv,0,sizeof(dv));
39         for(int i=0;i<=n;++i) d[i]=1;
40         ans=0;
41         for(int i=0;i<=n;++i) g[i].clear();
42         int l=0;
43         for(int i=1;i<=m;++i)
44         {
45             int a,b,c;
46             scanf("%d %d %d",&a,&b,&c);
47             e[l].to=b,e[l].flow=c,g[a].push_back(l);
48             ++l;
49             e[l].to=a,e[l].flow=0,g[b].push_back(l);
50             ++l;
51         }
52         dv[1]=n;
53         while(d[1]<=n) ans+=dfs(1,inf);
54         printf("%d\n",ans);
55     }
56     return 0;
57 }