최대 흐름 문제 의 Ford - Fulkerson 템 플 릿
다음은 나의 첫 번 째 가장 큰 흐름 의 문 제 를 붙인다.
hdu3549
1 #include<stdio.h>
2 #include<algorithm>
3 #include<stdlib.h>
4 #include<iostream>
5 #include<string.h>
6 #include<math.h>
7 #include<vector>
8 #include<map>
9 #include<queue>
10 struct pp
11 {
12 int x;
13 int cap;
14 int pre;
15 };
16 const int N=1e8;
17 bool used[30];
18 using namespace std;
19 vector<pp>GG[30];
20 void add(int from,int to,int vv)
21 { pp ss;
22 ss.cap=vv;ss.x=to;ss.pre=GG[to].size();
23 GG[from].push_back(ss);
24 ss.cap=0;ss.x=from;ss.pre=GG[from].size()-1;
25 GG[to].push_back(ss);
26 }
27 int dfs(int x,int y,int co)
28 {
29 if(x==y)
30 {
31 return co;
32 }
33 used[x]=true;
34 int i,j;
35 for(i=0;i<GG[x].size();i++)
36 { int cc ;
37 pp &LL=GG[x][i];
38 if(!used[LL.x]&&LL.cap>0)
39 {
40 cc=dfs(LL.x,y,min(co,LL.cap));
41 if(cc>0)
42 {
43 LL.cap-=cc;
44 GG[LL.x][LL.pre].cap+=cc;
45 return cc;
46 }
47 }
48 }
49 return 0;
50 }
51 int max_flow(int x,int t)
52 {
53 int flow=0;
54 while(1)
55 {memset(used,0,sizeof(used));
56 int kk=dfs(x,t,N);
57 if(kk==0)
58 {
59 return flow;
60 }
61 else flow+=kk;
62 }
63
64 }
65 int main(void)
66 {
67 int i,j,k,p,q;
68 scanf("%d",&k);
69
70 for(i=1;i<=k;i++)
71 { for(j=0;j<30;j++)
72 GG[j].clear();
73 scanf("%d %d",&p,&q);
74 int x;int y;int n,m;
75 for(j=0;j<q;j++)
76 {
77 scanf("%d %d %d",&x,&y,&n);
78 add(x,y,n);
79 }
80 int M=max_flow(1,p);
81 printf("Case %d: %d
",i,M);
82 }
83 return 0;
84 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.