网络流24题（部分）

这次的题全是老爷题yooo～
搭配飞行员

　　　　普通二分图，，，源点向正飞行员连1的边，有取向 :->的正副飞行员连1或inf的边，副飞行员和汇点连1的边，然后跑最大流

　　　　源/汇点向飞行员连的边一定要单独建= =

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 #define maxn 105
 7 #define maxm 3000
 8 #define inf 0x3f3f3f3f
 9 int cnt,v[maxm<<1],w[maxm<<1],next[maxm<<1],first[maxn];
10 int SSS,TTT,q[maxn],dep[maxn];
11 void add(int st,int end,int val){
12     v[cnt]=end;w[cnt]=val;next[cnt]=first[st];first[st]=cnt++;
13     v[cnt]=st;w[cnt]=0;next[cnt]=first[end];first[end]=cnt++;
14 }
15 bool bfs(){
16     int head=0,tail=0;
17     memset(dep,0,sizeof(dep));
18     q[++tail]=SSS;
19     dep[SSS]=1;
20     while(head<tail){
21         int x=q[++head];
22         for(int e=first[x];e!=-1;e=next[e]){
23             if(!dep[v[e]]&&w[e]>0){
24                 dep[v[e]]=dep[x]+1;
25                 q[++tail]=v[e];
26             }
27         }
28     }
29     return dep[TTT];
30 }
31 int dfs(int x,int lim){
32     if(x==TTT)return lim;
33     int lim1=lim;
34     for(int e=first[x];e!=-1;e=next[e]){
35         if(dep[v[e]]==dep[x]+1&&w[e]>0){
36             int flow=dfs(v[e],min(lim,w[e]));
37             w[e]-=flow;w[e^1]+=flow;
38             if((lim-=flow)<=0)break;
39         }
40     }
41     if(lim==lim1)dep[x]=0;
42     return lim1-lim;
43 }
44 int main(){
45     freopen("flyer.in","r",stdin);
46     freopen("flyer.out","w",stdout);
47     int n,n1,a,b;
48     memset(first,-1,sizeof(first));
49     scanf("%d%d",&n,&n1);
50     SSS=0,TTT=n+1;
51     for(int i=1;i<=n1;i++)add(SSS,i,1);
52     for(int i=n1+1;i<=n;i++)add(i,TTT,1);
53     while(scanf("%d%d",&a,&b)!=EOF)add(a,b,2);
54     int ans=0;
55     while(bfs())ans+=dfs(SSS,inf);
56     printf("%d
",ans);
57     fclose(stdin);
58     fclose(stdout);
59     return 0;
60 }

View Code

太空飞行计划

　　　　最大权闭合子图，666

　　　　源点向实验连权值为赞助额的边，实验向仪器连inf的边，仪器向汇点连权值为仪器开销的边，求出最小割。

　　　　最小割上的实验边代表不选的实验，因为开销>赞助额，从而使实验边满载；最小割上的仪器边代表要选的仪器，因为开销<=赞助额，从而使仪器边满载

　　　　由此可知答案为所有实验边的和减去最小割

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<vector>
  4 #include<ctype.h>
  5 using namespace std;
  6 #define maxn 2005
  7 #define maxm 105000
  8 #define inf 0x3f3f3f3f
  9 vector<int>poi[maxn];
 10 int cnt,v[maxm<<1],w[maxm<<1],next[maxm<<1],first[maxn],cur[maxn];
 11 int SSS,TTT,dep[maxn],q[maxn],have[maxn],you[maxn];
 12 void read(int i){    
 13     char ch=0;
 14     while(1){
 15         while(!isdigit(ch))
 16             ch=getchar();
 17         int tmp=0;
 18         while(isdigit(ch)){
 19             tmp=tmp*10+ch-'0';
 20             ch=getchar();
 21         }
 22         poi[i].push_back(tmp);
 23         if(ch=='
')return;
 24     }
 25 }
 26 void add(int st,int end,int val){
 27     v[cnt]=end;w[cnt]=val;next[cnt]=first[st];first[st]=cnt++;
 28     v[cnt]=st;w[cnt]=0;next[cnt]=first[end];first[end]=cnt++;
 29 }
 30 bool bfs(){
 31     int head=0,tail=0;
 32     memset(dep,0,sizeof(dep));
 33     q[++tail]=SSS;
 34     dep[SSS]=1;
 35     while(head<tail){
 36         int x=q[++head];
 37         for(int e=first[x];e!=-1;e=next[e]){
 38             if(!dep[v[e]]&&w[e]>0){
 39                 dep[v[e]]=dep[x]+1;
 40                 q[++tail]=v[e];
 41             }
 42         }
 43     }
 44     return dep[TTT];
 45 }
 46 int dfs(int x,int lim){
 47     if(x==TTT)return lim;
 48     int lim1=lim;
 49     for(int e=cur[x];e!=-1;e=next[e]){
 50         if(dep[v[e]]==dep[x]+1&&w[e]>0){
 51             int flow=dfs(v[e],min(lim,w[e]));
 52             cur[x]=e;
 53             w[e]-=flow;w[e^1]+=flow;
 54             if((lim-=flow)<=0)break;
 55         }
 56     }
 57     if(lim==lim1)dep[x]=0;
 58     return lim1-lim;
 59 }
 60 int main(){
 61     freopen("shuttle.in","r",stdin);
 62     freopen("shuttle.out","w",stdout);
 63     int n,m,x;
 64     memset(first,-1,sizeof(first));
 65     scanf("%d%d",&n,&m);
 66     SSS=0,TTT=n+m+1;
 67     int sum=0;
 68     for(int i=1;i<=n;i++){
 69         scanf("%d",&x);
 70         sum+=x;
 71         add(SSS,i,x);
 72         read(i);
 73     }
 74     for(int i=1;i<=m;i++){
 75         scanf("%d",&x);
 76         add(i+n,TTT,x);
 77     }
 78     for(int i=1;i<=n;i++)
 79         for(int j=0;j<poi[i].size();j++)
 80             add(i,poi[i][j]+n,inf);
 81     int ans=0;
 82     while(bfs()){
 83         memcpy(cur,first,sizeof(first));
 84         ans+=dfs(SSS,inf);
 85     }
 86     for(int e=first[SSS];e!=-1;e=next[e])
 87         if(dep[v[e]])have[v[e]]=1;
 88     for(int i=1;i<=n;i++)
 89         if(have[i]){
 90             printf("%d ",i);
 91             for(int j=0;j<poi[i].size();j++)
 92                 you[poi[i][j]]=1;
 93         }
 94     printf("
");
 95     for(int i=1;i<=m;i++)
 96         if(you[i])printf("%d ",i);
 97     printf("
%d
",sum-ans);
 98     fclose(stdin);
 99     fclose(stdout);
100     return 0;
101 }

View Code

最小路径覆盖问题

　　　　可以转化成二分图最大匹配，因为每匹配一条边就少一条路径。因为要输出方案，所以写了匈牙利。。。

　　　　把每个点拆成两个，原图中有边的两个点之间有配对倾向。路径数为点数-最大匹配数，输出方案就可以在belong数组，或map数组上luogan

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 #define maxn 305
 5 #define maxm 6005
 6 int cnt,v[maxm<<1],next[maxm<<1],first[maxn];
 7 int used[maxn],belong[maxn],map[maxn],vis[maxn];
 8 
 9 void add(int st,int end){
10     v[++cnt]=end;
11     next[cnt]=first[st];
12     first[st]=cnt;
13 }
14 bool find(int x){
15     for(int e=first[x];e;e=next[e]){
16         if(!used[v[e]]){
17             used[v[e]]=1;
18             if(!belong[v[e]]||find(belong[v[e]])){
19                 belong[v[e]]=x;
20                 map[x]=v[e];
21                 return true;
22             }
23         }
24     }
25     return false;
26 }
27 int main(){
28     freopen("path3.in","r",stdin);
29     freopen("path3.out","w",stdout);
30     int n,m,a,b;
31     scanf("%d%d",&n,&m);
32     for(int i=1;i<=m;i++){
33         scanf("%d%d",&a,&b);
34         add(a,b+n);
35     }
36     int ans=0;
37     for(int i=1;i<=n;i++){
38         for(int j=n;j<=2*n;j++)used[j]=0;
39         if(find(i))ans++;
40     }
41     for(int i=1;i<=n;i++){
42         if(!vis[i]){
43             int ii=i;
44             while(ii>0){
45                 printf("%d ",ii);
46                 vis[ii]=1;
47                 ii=map[ii]-n;
48             }
49             printf("
");
50         }
51     }
52     printf("%d
",n-ans);
53     fclose(stdin);
54     fclose(stdout);
55     return 0;
56 }

View Code

　　　　Dinic算法请见友链中的y7070. http://www.cnblogs.com/y7070/p/4988800.html

bzoj3996

　　　　给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得D=（A*B-C）*A^T最大。其中A^T为A的转置。输出D

　　　　首先学习了一个转置，Bij=Aji，然后推公式！！！

　　　　wsh大爷教育的是，for循环分析法，于是有

　　　　（然而有老爷严谨的证明，，，这里就不写了）

　　　　于是发现这个式子是最大权闭合子图的yooo～

　　　　因为Bij有贡献，当且仅当Ai和Aj都不为0，然而这样Ci和Cj也会对答案产生负的贡献，因为是闭合子图

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 #define inf 0x3f3f3f3f
 7 #define maxn 250505
 8 #define maxm 750505
 9 int cnt,v[maxm<<1],w[maxm<<1],next[maxm<<1],first[maxn],cur[maxn];
10 int SSS,TTT,dep[maxn],q[maxn];
11 
12 void add(int st,int end,int val){
13     v[cnt]=end;w[cnt]=val;next[cnt]=first[st];first[st]=cnt++;
14     v[cnt]=st;w[cnt]=0;next[cnt]=first[end];first[end]=cnt++;
15 }
16 bool bfs(){
17     memset(dep,0,sizeof(dep));
18     int head=0,tail=0;
19     q[++tail]=SSS;
20     dep[SSS]=1;
21     while(head<tail){
22         int x=q[++head];
23         for(int e=first[x];e!=-1;e=next[e]){
24             if(!dep[v[e]]&&w[e]>0){
25                 dep[v[e]]=dep[x]+1;
26                 q[++tail]=v[e];
27             }
28         }
29     }
30     return dep[TTT];
31 }
32 int dfs(int x,int lim){
33     if(x==TTT)return lim;
34     int lim1=lim;
35     for(int e=cur[x];e!=-1;e=next[e]){
36         if(dep[v[e]]==dep[x]+1&&w[e]>0){
37             int flow=dfs(v[e],min(lim,w[e]));
38             cur[x]=e;
39             w[e]-=flow;w[e^1]+=flow;
40             if((lim-=flow)<=0)break;
41         }
42     }
43     if(lim1==lim)dep[x]=0;
44     return lim1-lim;
45 }
46 int main(){
47     freopen("1.in","r",stdin);
48     memset(first,-1,sizeof(first));
49     int n,b,c;
50     scanf("%d",&n);
51     SSS=0,TTT=n*n+n+1;
52     int sum=0;
53     for(int i=1;i<=n;i++)
54         for(int j=1;j<=n;j++){
55             scanf("%d",&b);
56             sum+=b;
57             add(SSS,(i-1)*n+j,b);
58             add((i-1)*n+j,n*n+i,inf);
59             add((i-1)*n+j,n*n+j,inf);
60         }
61     for(int i=1;i<=n;i++){
62         scanf("%d",&c);
63         add(n*n+i,TTT,c);
64     }
65     int ans=0;
66     while(bfs()){
67         memcpy(cur,first,sizeof(first));
68         ans+=dfs(SSS,inf);
69     }
70     printf("%d
",sum-ans);
71     return 0;
72 }

View Code∑ni=1∑nj=1Bij×Ai×Aj–∑ni=1Ai×Ci

魔术球问题

　　　最小路径覆盖，建边鬼畜。。。二分答案，判断所需的最小路径数与读入的n的大小关系，，，艾斯比的我还输出了方案，QAQ

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 #define maxans 1600
 5 #define maxn 1605
 6 #define maxm 35000
 7 int cnt,v[maxm],next[maxm],first[maxn];
 8 int n,belong[maxn<<1],used[maxn<<1];//map[maxn],vis[maxn];
 9 
10 void add(int st,int end){
11     v[++cnt]=end;
12     next[cnt]=first[st];
13     first[st]=cnt;
14 }
15 bool find(int x){
16     for(int e=first[x];e;e=next[e]){
17         if(!used[v[e]]){
18             used[v[e]]=1;
19             if(!belong[v[e]]||find(belong[v[e]])){
20                 belong[v[e]]=x;
21                 //map[x]=v[e];
22                 return true;
23             }
24         }
25     }
26     return false;
27 }
28 bool can(int x){
29     cnt=0;
30     memset(first,0,sizeof(first));
31     int xx=2*x;
32     for(int i=2;i*i<2*xx;i++){
33         int m=i*i;
34         for(int j=1;j<=m/2;j++)
35             if(j!=m-j&&j<=x&&m-j<=x)
36                 add(j,m-j+x);
37     }
38     int ans=0;
39     memset(belong,0,sizeof(belong));
40     //memset(map,0,sizeof(map));
41     for(int i=1;i<=x;i++){
42         memset(used,0,sizeof(used));
43         if(find(i))ans++;
44     }
45     return x-ans<=n;
46 }
47 int main(){
48     freopen("balla.in","r",stdin);
49     freopen("balla.out","w",stdout);
50     scanf("%d",&n);
51     int l=0,r=maxans+1;
52     while(l<r-1){
53         int mid=(l+r)>>1;
54         if(can(mid))l=mid;
55         else r=mid;
56     }
57     //can(l);
58     printf("%d
",l);
59     /*for(int i=1;i<=l;i++)
60         if(!vis[i]){
61             int ii=i;
62             while(ii>0){
63                 printf("%d ",ii);
64                 vis[ii]=1;
65                 ii=map[ii]-l;
66             }
67             printf("
");
68        }
69     */
70     fclose(stdin);
71     fclose(stdout);
72     return 0;
73 }

View Code

圆桌聚餐

　　　水题乱搞　　

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 #define inf 0x3f3f3f3f
 7 #define maxn 450
 8 #define maxm 41000
 9 int cnt,v[maxm<<1],next[maxm<<1],w[maxm<<1],first[maxn];
10 int SSS,TTT,dep[maxn],q[maxn];
11 
12 void add(int st,int end,int val){
13     v[cnt]=end;w[cnt]=val;next[cnt]=first[st];first[st]=cnt++;
14     v[cnt]=st;w[cnt]=0;next[cnt]=first[end];first[end]=cnt++;
15 }
16 bool bfs(){
17     int head=0,tail=0;
18     memset(dep,0,sizeof(dep));
19     q[++tail]=SSS;
20     dep[SSS]=1;
21     while(head<tail){
22         int x=q[++head];
23         for(int e=first[x];e!=-1;e=next[e]){
24             if(!dep[v[e]]&&w[e]>0){
25                 dep[v[e]]=dep[x]+1;
26                 q[++tail]=v[e];
27             }
28         }
29     }
30     return dep[TTT];
31 }
32 int dfs(int x,int lim){
33     if(x==TTT)return lim;
34     int lim1=lim;
35     for(int e=first[x];e!=-1;e=next[e]){
36         if(dep[v[e]]==dep[x]+1&&w[e]>0){
37             int flow=dfs(v[e],min(lim,w[e]));
38             w[e]-=flow;w[e^1]+=flow;
39             if((lim-=flow)<=0)break;
40         }
41     }
42     if(lim==lim1)dep[x]=0;
43     return lim1-lim;
44 }
45 int main(){
46     freopen("roundtable.in","r",stdin);
47     freopen("roundtable.out","w",stdout);
48     int n,m,x;
49     memset(first,-1,sizeof(first));
50     scanf("%d%d",&n,&m);
51     SSS=0,TTT=n+m+1;
52     int sum=0,maxp=0;
53     for(int i=1;i<=n;i++){
54         scanf("%d",&x);
55         sum+=x;
56         maxp=max(maxp,x);
57         add(SSS,i,x);
58         for(int j=1;j<=m;j++)
59             add(i,n+j,1);
60     }
61     if(maxp>m){
62         printf("0
");
63         return 0;
64     }
65     for(int i=1;i<=m;i++){
66         scanf("%d",&x);
67         add(n+i,TTT,x);
68     }
69     int ans=0;
70     while(bfs())ans+=dfs(SSS,inf);
71     if(ans==sum){
72         printf("1
");
73         for(int x=1;x<=n;x++){
74             for(int e=first[x];e!=-1;e=next[e])
75                 if(!w[e])printf("%d ",v[e]-n);
76             printf("
");
77         }   
78     }
79     else printf("0
");
80     fclose(stdin);
81     fclose(stdout);
82     return 0;
83 }

View Code

最长递增子序列问题

　　　　①dp

　　　　②网络流建图，拆点，能组成递增子序列的点之间连边，，，自己和建边！！！

　　　　③改下流量限制，lg

 1     #include<stdio.h>
 2     #include<algorithm>
 3     #include<string.h>
 4     using namespace std;
 5     #define maxn 1010
 6     #define maxm 251005
 7     #define inf 0x3f3f3f3f
 8     int cnt,v[maxm<<1],w[maxm<<1],next[maxm<<1],first[maxn];
 9     int n,haha,SSS,TTT,k,dep[maxn],q[maxn],f[maxn],a[maxn];
10     void add(int st,int end,int val){
11         v[cnt]=end;w[cnt]=val;next[cnt]=first[st];first[st]=cnt++;
12         v[cnt]=st;w[cnt]=0;next[cnt]=first[end];first[end]=cnt++;
13     }
14     int solve1(){
15        for(int i=1;i<=n;i++){
16             scanf("%d",&a[i]);
17             f[i]=1;
18             for(int j=1;j<i;j++)
19                 if(a[i]>=a[j])f[i]=max(f[i],f[j]+1);
20             k=max(k,f[i]);
21         }
22        printf("%d
",k);
23     }
24     bool bfs(){
25         memset(dep,0,sizeof(dep));
26         int head=0,tail=0;
27         q[++tail]=SSS;
28         dep[SSS]=1;
29         while(head<tail){
30             int x=q[++head];
31             for(int e=first[x];e!=-1;e=next[e]){
32                 if(!dep[v[e]]&&w[e]>0){
33                     dep[v[e]]=dep[x]+1;
34                     q[++tail]=v[e];
35                 }
36             }
37         }
38         return dep[TTT];
39     }
40     int dfs(int x,int lim){
41         if(x==TTT)return lim;
42         int lim1=lim;
43         for(int e=first[x];e!=-1;e=next[e]){
44             if(dep[v[e]]==dep[x]+1&&w[e]>0){
45                 int flow=dfs(v[e],min(lim,w[e]));
46                 w[e]-=flow;w[e^1]+=flow;
47                 if((lim-=flow)<=0)break;
48             }
49         }
50         if(lim1==lim)dep[x]=0;
51         return lim1-lim;
52     }
53     void solve2(){
54         memset(first,-1,sizeof(first));
55         SSS=0,TTT=2*n+1;
56         for(int i=1;i<=n;i++){
57             if(f[i]==1)add(SSS,i,1);
58             if(f[i]==k)add(i+n,TTT,1);
59             add(i,i+n,1);
60         }
61         for(int i=1;i<=n;i++)
62             for(int j=i+1;j<=n;j++)
63                 if(a[j]>=a[i]&&f[j]==f[i]+1)add(i+n,j,1);
64         while(bfs())haha+=dfs(SSS,inf);
65         printf("%d
",haha);
66     }
67     void solve3(){
68         memset(first,-1,sizeof(first));
69         SSS=0,TTT=2*n+1;
70         for(int i=1;i<=n;i++){
71         int v=1;
72         if(i==1||i==n)v=inf;
73             if(f[i]==1)add(SSS,i,v);
74             if(f[i]==k)add(i+n,TTT,v);
75             add(i,i+n,v);
76         }
77         for(int i=1;i<=n;i++)
78             for(int j=i+1;j<=n;j++)
79                 if(a[j]>=a[i]&&f[j]==f[i]+1)add(i+n,j,1);
80         int ans=0;
81         while(bfs())ans+=dfs(SSS,inf);
82         if(ans>=inf)ans=haha;
83         printf("%d
",ans);
84     }
85     int main(){
86         freopen("alis.in","r",stdin);
87         freopen("alis.out","w",stdout);
88         scanf("%d",&n);
89         solve1();
90         solve2();
91         solve3();
92         fclose(stdin);
93         fclose(stdout);
94         return 0;
95     }

View Code

方格取数

　　　　最大独立集=点数-最小点覆盖=点数-最小割或最大独立集-点数-最小点覆盖=点数-最大匹配=点数-最大流

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 #define maxn 1805
 7 #define maxm 3665
 8 #define inf 0x3f3f3f3f
 9 int cnt,v[maxm<<1],w[maxm<<1],next[maxm<<1],first[maxn];
10 int SSS,TTT,dep[maxn],q[maxn];
11 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
12 void add(int st,int end,int val){
13     v[cnt]=end;w[cnt]=val;next[cnt]=first[st];first[st]=cnt++;
14     v[cnt]=st;w[cnt]=0;next[cnt]=first[end];first[end]=cnt++;
15 }
16 bool bfs(){
17     int head=0,tail=0;
18     memset(dep,0,sizeof(dep));
19     dep[SSS]=1;
20     q[++tail]=SSS;
21     while(head<tail){
22         int x=q[++head];
23         for(int e=first[x];e!=-1;e=next[e]){
24             if(!dep[v[e]]&&w[e]>0){
25                 dep[v[e]]=dep[x]+1;
26                 q[++tail]=v[e];
27             }
28         }
29     }
30     return dep[TTT];
31 }
32 
33 int dfs(int x,int lim){
34     if(x==TTT)return lim;
35     int lim1=lim;
36     for(int e=first[x];e!=-1;e=next[e]){
37         if(dep[v[e]]==dep[x]+1&&w[e]>0){
38             int flow=dfs(v[e],min(lim,w[e]));
39             w[e]-=flow;w[e^1]+=flow;
40             if((lim-=flow)<=0)break;
41         }
42     }
43     if(lim==lim1)dep[x]=0;
44     return lim1-lim;
45 }
46 int main(){
47     freopen("1.in","r",stdin);
48     memset(first,-1,sizeof(first));
49     int n,m,x;
50     scanf("%d%d",&n,&m);
51     int haha=n*m;
52     SSS=0,TTT=2*haha+1;
53     int sum=0;
54     for(int i=1;i<=n;i++)
55         for(int j=1;j<=m;j++){
56             scanf("%d",&x);
57             sum+=x;
58             add(SSS,(i-1)*m+j,x);
59             add(haha+(i-1)*m+j,TTT,x);
60             for(int k=0;k<4;k++){
61                 int ii=i+dir[k][0],jj=j+dir[k][1];
62                 if(ii>=1&&ii<=n&&jj>=1&&jj<=m)
63                     add((i-1)*m+j,haha+(ii-1)*m+jj,inf);
64             }
65         }
66     int ans=0;
67     while(bfs())ans+=dfs(SSS,inf);
68     printf("%d
",ans);
69     return 0;
70 }

View Code

餐巾问题

　　费用流第一道题，yooo～

　　建图超神，拆点，两个点集分别代表今天要用的来源和今天用完的去向，然后依题意lg，加上流量限制，保证能满流

　　写了两种，辣鸡班，和伪·重口味版，，，然而多路增广更慢是什么鬼

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 #define inf 0x3f3f3f3f
 6 #define maxn 405
 7 #define maxm  1205
 8 int cnt,u[maxm<<1],v[maxm<<1],w[maxm<<1],c[maxm<<1],next[maxm<<1],first[maxn];
 9 int N,cost,SSS,TTT,dist[maxn],q[maxn],pre[maxn];
10 bool vis[maxn];
11 
12 void add(int st,int end,int val,int cos){
13     u[cnt]=st;v[cnt]=end;w[cnt]=val;c[cnt]=cos;next[cnt]=first[st];first[st]=cnt++;
14     u[cnt]=end;v[cnt]=st;w[cnt]=0;c[cnt]=-cos;next[cnt]=first[end];first[end]=cnt++;
15 }
16 bool spfa(){
17     int head=0,tail=0;
18     memset(dist,0x3f,sizeof(dist));
19     memset(vis,false,sizeof(vis));
20     q[tail++]=SSS;
21     vis[SSS]=true;
22     dist[SSS]=0;
23     pre[SSS]=-1;
24     int nn=2*N+2;
25     while(head!=tail){
26         int x=q[head];
27         if(++head==nn)head=0;
28         for(int e=first[x];e!=-1;e=next[e]){
29             if(w[e]>0&&dist[v[e]]>dist[x]+c[e]){
30                 pre[v[e]]=e;
31                 dist[v[e]]=dist[x]+c[e];
32                 if(!vis[v[e]]){
33                     vis[v[e]]=true;
34                     q[tail]=v[e];
35                     if(++tail==nn)tail=0;
36                 }
37             }
38         }
39         vis[x]=false;
40     }
41     return dist[TTT]!=inf;
42 }
43 void haha(){
44     int minf=inf,e=pre[TTT];
45     while(e!=-1){
46         minf=min(minf,w[e]);
47         e=pre[u[e]];
48     }
49     e=pre[TTT];
50     while(e!=-1){
51         w[e]-=minf;
52         w[e^1]+=minf;
53         cost+=minf*c[e];
54         e=pre[u[e]];
55     }
56 }
57 int main(){
58     freopen("napkin.in","r",stdin);
59     freopen("napkin.out","w",stdout);
60     memset(first,-1,sizeof(first));
61     scanf("%d",&N);
62     SSS=0,TTT=2*N+1;
63     for(int i=1;i<=N;i++){
64         int x;
65         scanf("%d",&x);
66         add(SSS,i,x,0);
67         add(i+N,TTT,x,0);
68     }
69     int p,m,f,n,s;
70     scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
71     for(int i=1;i<=N;i++){
72         add(SSS,i+N,inf,p);
73         if(i+1<=N)add(i,i+1,inf,0);
74         if(i+m<=N)add(i,N+i+m,inf,f);
75         if(i+n<=N)add(i,N+i+n,inf,s);
76     }
77     while(spfa())haha();
78     printf("%d
",cost);
79     fclose(stdin);
80     fclose(stdout);
81     return 0;
82 }

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 #define inf 0x3f3f3f3f
 7 #define maxn 405
 8 #define maxm 1205
 9 int cnt,v[maxm<<1],w[maxm<<1],c[maxm<<1],next[maxm<<1],first[maxn];
10 int N,ans,SSS,TTT,dist[maxn],q[maxn],vis[maxn];
11 
12 void add(int st,int end,int val,int cos){
13     v[cnt]=end;w[cnt]=val;c[cnt]=cos;next[cnt]=first[st];first[st]=cnt++;
14     v[cnt]=st;w[cnt]=0;c[cnt]=-cos;next[cnt]=first[end];first[end]=cnt++;
15 }
16 bool spfa(){
17     for(int i=SSS;i<=TTT;i++){
18         vis[i]=0;
19         dist[i]=inf;
20     }
21     int head=0,tail=0;
22     q[tail++]=SSS;dist[SSS]=0;vis[SSS]=1;
23     int nn=2*N+2;
24     while(head!=tail){
25         int x=q[head];
26         if(++head==nn)head=0;
27         for(int e=first[x];e!=-1;e=next[e]){
28             if(w[e]>0&&dist[v[e]]>dist[x]+c[e]){
29                 dist[v[e]]=dist[x]+c[e];
30                 if(!vis[v[e]]){
31                     vis[v[e]]=1;
32                     q[tail]=v[e];
33                     if(++tail==nn)tail=0;
34                 }
35             }
36         }
37         vis[x]=0;
38     }
39     return dist[TTT]!=inf;
40 }
41 int dfs(int x,int lim){
42     if(x==TTT)return lim;
43     int lim1=lim;
44     for(int e=first[x];e!=-1;e=next[e]){
45         if(!vis[v[e]]&&w[e]>0&&dist[v[e]]==dist[x]+c[e]){
46             vis[v[e]]=1;
47             int flow=dfs(v[e],min(lim,w[e]));
48             w[e]-=flow;w[e^1]+=flow;
49             ans+=flow*c[e];
50             if((lim-=flow)<=0)break;
51         }
52     }
53     if(lim==lim1)dist[x]=inf;
54     return lim1-lim;
55 }
56 int main(){
57     freopen("napkin.in","r",stdin);
58     freopen("napkin.out","w",stdout);
59     int x,p,m,f,n,s;
60     memset(first,-1,sizeof(first));
61     scanf("%d",&N);
62     SSS=0,TTT=2*N+1;
63     for(int i=1;i<=N;i++){
64         scanf("%d",&x);
65         add(SSS,i,x,0);
66         add(i+N,TTT,x,0);
67     }
68     scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
69     for(int i=1;i<=N;i++){
70         add(SSS,i+N,inf,p);
71         if(i+1<=N)add(i,i+1,inf,0);
72         if(i+m<=N)add(i,i+N+m,inf,f);
73         if(i+n<=N)add(i,i+N+n,inf,s);
74     }
75     int yooo=0;
76     while(spfa()){
77         memset(vis,0,sizeof(vis));
78         vis[SSS]=1;
79         yooo+=dfs(SSS,inf);
80     }
81     printf("%d
",ans);
82     fclose(stdin);
83     fclose(stdout);
84     return 0;
85 }

View Code

航空路线问题

　　最大费用最大流，，，注意和起点还有终点相连的边的流量都应为2

　　其实有两问，第二问依次输出经过的城市，然而并没有找到能在哪提交，于是。。。没写第二问，监介。。。

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<map>
 4 #include<string>
 5 #include<string.h>
 6 using namespace std;
 7 
 8 #define inf 0x3f3f3f3f
 9 #define maxn 105
10 #define maxm 10105
11 int cnt,v[maxm<<1],w[maxm<<1],c[maxm<<1],next[maxm<<1],first[maxn];
12 int n,m,SSS,TTT,cost,dist[maxn],vis[maxn],q[maxn];
13 string str1,str2;
14 map<string,int>Map;
15 
16 void add(int st,int end,int val,int cos){
17     v[cnt]=end;w[cnt]=val;c[cnt]=cos;next[cnt]=first[st];first[st]=cnt++;
18     v[cnt]=st;w[cnt]=0;c[cnt]=-cos;next[cnt]=first[end];first[end]=cnt++;
19 }
20 bool spfa(){
21     for(int i=SSS;i<=TTT;i++){
22         dist[i]=inf;
23         vis[i]=0;
24     }
25     int head=0,tail=0;
26     q[tail++]=SSS;vis[SSS]=1;dist[SSS]=0;
27     while(head!=tail){
28         int x=q[head];
29         if(++head==n)head=0;
30         for(int e=first[x];e!=-1;e=next[e]){
31             if(w[e]>0&&dist[v[e]]>dist[x]+c[e]){
32                 dist[v[e]]=dist[x]+c[e];
33                 if(!vis[v[e]]){
34                     vis[v[e]]=1;
35                     q[tail]=v[e];
36                     if(++tail==n)tail=0;
37                 }
38             }
39         }
40         vis[x]=0;
41     }
42     return dist[TTT]!=inf;
43 }
44 int dfs(int x,int lim){
45     if(x==TTT)return lim;
46     int lim1=lim;
47     for(int e=first[x];e!=-1;e=next[e]){
48         if(!vis[v[e]]&&w[e]>0&&dist[v[e]]==dist[x]+c[e]){
49             vis[v[e]]=1;
50             int flow=dfs(v[e],min(lim,w[e]));
51             w[e]-=flow;w[e^1]+=flow;
52             cost+=flow*c[e];
53             if((lim-=flow)<=0)break;
54         }
55     }
56     if(lim==lim1)dist[x]=inf;
57     return lim1-lim;
58 }
59 int main(){
60     //freopen("1.in","r",stdin);
61     memset(first,-1,sizeof(first));
62     scanf("%d%d",&n,&m);
63     SSS=1,TTT=2*n;
64     for(int i=1;i<=n;i++){
65         cin>>str1;
66         Map[str1]=i;
67         if(i==1||i==n)add(i,i+n,2,0);
68         else add(i,i+n,1,0);
69     }
70     for(int i=1;i<=m;i++){
71         cin>>str1>>str2;
72         int a=Map[str1],b=Map[str2];
73         if(a<b){
74             if(a==1&&b==n)add(a+n,b,2,-1);
75             else add(a+n,b,1,-1);
76         }
77         else{
78             if(a==1&&b==n)add(b+n,a,2,-1);
79             add(b+n,a,1,-1);
80         }
81     }
82     int ans=0;
83     while(spfa()){
84         memset(vis,0,sizeof(vis));
85         vis[SSS]=1;
86         ans+=dfs(SSS,inf);
87     }
88     if(ans!=2)printf("No Solution!
");
89     else printf("%d
",-cost);
90     return 0;
91 }

View Code

星际转移

　　建图建的要飞起来了，，，调了一天，然而发现是每次都把ans初始化了，，，然而这道题是每枚举一个就在原来的图上添边，而且原来的也增广过了，于是haha

 1     #include<stdio.h>
 2     #include<vector>
 3     #include<string.h>
 4     #include<algorithm>
 5     using namespace std;
 6      
 7     #define inf 0x3f3f3f3f
 8     #define maxn 1005
 9     #define maxm 10005
10     vector<int>V[25];
11     int cnt,v[maxm<<1],w[maxm<<1],next[maxm<<1],first[maxn],cur[maxn];
12     int ans,SSS,TTT,n,m,k,dep[maxn],q[maxn],h[25],p[25],fa[maxn];
13      
14     void add(int st,int end,int val){
15         v[cnt]=end;w[cnt]=val;next[cnt]=first[st];first[st]=cnt++;
16         v[cnt]=st;w[cnt]=0;next[cnt]=first[end];first[end]=cnt++;
17     }
18     int getf(int x){
19         return fa[x]=fa[x]==x?x:getf(fa[x]);
20     }
21     int haha(int day,int t){
22         return n*day+t;
23     }
24     bool bfs(){
25         int head=0,tail=0;
26         memset(dep,0,sizeof(dep));
27         q[++tail]=SSS;
28         dep[SSS]=1;
29         while(head<tail){
30             int x=q[++head];
31             for(int e=first[x];e!=-1;e=next[e]){
32                 if(!dep[v[e]]&&w[e]>0){
33                     dep[v[e]]=dep[x]+1;
34                     q[++tail]=v[e];
35                 }
36             }
37         }
38         return dep[TTT];
39     }
40     int dfs(int x,int lim){
41         if(x==TTT)return lim;
42         int lim1=lim;
43         for(int &e=cur[x];e!=-1;e=next[e]){
44             if(w[e]>0&&dep[v[e]]==dep[x]+1){
45                 int flow=dfs(v[e],min(lim,w[e]));
46                 w[e]-=flow;w[e^1]+=flow;
47                 if((lim-=flow)<=0)break;
48             }
49         }
50         if(lim==lim1)dep[x]=0;
51         return lim1-lim;
52     }
53     bool can(int x){
54         add(SSS,haha(x,n),inf);
55         add(haha(x,n-1),TTT,inf);
56         for(int i=1;i<=n;i++)
57             add(haha(x-1,i),haha(x,i),inf);
58         for(int i=1;i<=m;i++)
59             add(haha(x-1,V[i][(x-1)%p[i]]),haha(x,V[i][x%p[i]]),h[i]);
60         while(bfs()){
61             memcpy(cur,first,sizeof(first));
62             ans+=dfs(SSS,inf);
63         }
64         return ans>=k;
65     }
66     int main(){
67         freopen("home.in","r",stdin);
68         freopen("home.out","w",stdout);
69         memset(first,-1,sizeof(first));
70         scanf("%d%d%d",&n,&m,&k);
71         SSS=1000,TTT=1001;
72         n+=2;
73         for(int i=1;i<=n;i++)fa[i]=i;
74         for(int i=1;i<=m;i++){
75             scanf("%d%d",&h[i],&p[i]);
76             for(int j=0;j<p[i];j++){
77                 int x;
78                 scanf("%d",&x);
79                 if(x==0)x=n;
80                 if(x==-1)x=n-1;
81                 V[i].push_back(x);
82                 if(j)fa[getf(V[i][j-1])]=getf(x);
83             }
84             fa[getf(V[i][0])]=getf(V[i][p[i]-1]);
85         }
86         if(getf(n-1)!=getf(n))printf("0
");
87         else {
88             add(SSS,haha(0,n),inf);
89             add(haha(0,n-1),TTT,inf);
90             for(int i=1;;i++)
91                 if(can(i)){
92                     printf("%d
",i);
93                     break;
94                 }
95         }
96         fclose(stdin);
97         fclose(stdout);
98         return 0;
99     }

View Code