网络流24T

说出来你们可能不信，我咕了三个多星期了，今晚忽然不想再写题了，(写自闭了，把这边整理一下

1. 洛谷P2756 飞行员配对问题

二分图匹配：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int m,n,a,b;
 4 const int MAXN = 105;
 5 int g[MAXN][MAXN];
 6 int linker[MAXN],used[MAXN];
 7 bool dfs(int u){
 8     for(int v=1;v<=n;v++){
 9         if(g[u][v]&&!used[v]){
10             used[v]=true;
11             if(linker[v]==-1||dfs(linker[v])){
12                 linker[v]=u;//这俩匹配上了
13                 return true;
14             }
15         }
16     }
17     return false;
18 }
19 int hungary(){
20     int res = 0;
21     memset(linker,-1, sizeof(linker));
22     for(int u=1;u<=m;u++){
23         memset(used,0, sizeof(used));
24         if(dfs(u))
25             res++;
26     }
27     return res;
28 }
29 int main(){
30     ios::sync_with_stdio(false);
31     cin>>m>>n;
32     while (cin>>a>>b&&a!=-1&&b!=-1){
33         g[a][b]=1;
34     }
35     cout<<hungary()<<endl;
36     for(int i=1;i<=n;i++){
37         if(linker[i]!=-1)
38             cout<<linker[i]<<' '<<i<<endl;
39     }
40 }

View Code

最大流EK：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 struct edge{
 5     int to,cap,rev;
 6 };
 7 vector<edge> g[250];
 8 bool used[250];
 9 void addEdge(int from,int to,int cap){//s到t流量为cap
10     g[from].push_back((edge){to,cap,g[to].size()});
11     g[to].push_back((edge){from,0,g[from].size()-1});
12 }
13 int dfs(int v,int t,int f){
14     if(v==t)
15         return f;
16     used[v]=true;
17     for(int i=0;i<g[v].size();i++){
18         edge &e = g[v][i];
19         if(!used[e.to]&&e.cap>0){//这算法竟该死的朴实
20             int d = dfs(e.to,t,min(f,e.cap));
21             if(d>0){
22                 e.cap-=d;
23                 g[e.to][e.rev].cap+=d;
24                 return d;
25             }
26         }
27     }
28     return 0;
29 }
30 int max_flow(int s,int t){
31     int flow = 0;
32     for(;;){
33         memset(used,0, sizeof(used));
34         int f = dfs(s,t,INF);
35         if(f==0) return flow;
36         flow += f;
37     }
38 }
39 int m,n,a,b;
40 int main(){
41     ios::sync_with_stdio(false);
42     cin>>m>>n;
43     while (cin>>a>>b&&a!=-1&&b!=-1){
44         addEdge(a,b+m,1);
45     }
46     int S = 0,END = m+n+1;
47     for(int i=1;i<=m;i++){
48         addEdge(S,i,1);
49     }
50     for(int i=m+1;i<=m+n;i++){
51         addEdge(i,END,1);
52     }
53     cout<<max_flow(0,n+m+1)<<endl;
54     for(int i=1;i<=m;i++){
55         for(int j=0;j<g[i].size();j++) {
56             edge tmp = g[i][j];
57             if (tmp.cap == 0&&g[i][j].to!=0) {
58                 cout << i<<' '<<g[i][j].to-m<<endl;
59                 break;
60             }
61         }
62     }
63 }

View Code

2.P4016 负载平衡问题

费用流，首先相邻的仓库连流量INF费用为1的边。然后我们算出来平均数ave，如果这个仓库货物大于ave，就从源点连一个a[i]-ave的边，小于的话向汇点连一个ave-a[i]的边。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int MAXN = 10000;
  4 const int MAXM = 100000;
  5 const int INF = 0x3f3f3f3f;
  6 struct Edge{
  7     int to,next,cap,flow,cost;
  8 }edge[MAXM];
  9 int head[MAXN],tol;
 10 int pre[MAXN],dis[MAXN];
 11 bool vis[MAXN];
 12 int N;
 13 void init(int all){
 14     N = all;
 15     tol = 0;
 16     memset(head,-1, sizeof(head));
 17 }
 18 void addEdge(int u,int v,int cap,int cost){
 19     edge[tol].to=v;
 20     edge[tol].cap = cap;
 21     edge[tol].cost = cost;
 22     edge[tol].flow =0 ;
 23     edge[tol].next = head[u];
 24     head[u]=tol++;
 25     edge[tol].to=u;
 26     edge[tol].cap = 0;
 27     edge[tol].cost= -cost;
 28     edge[tol].flow=0;
 29     edge[tol].next=head[v];
 30     head[v]=tol++;
 31 }
 32 bool spfa(int s,int t){
 33     queue<int> q;
 34     for(int i=0;i<N;i++){
 35         dis[i]=INF;
 36         vis[i] = false;
 37         pre[i]=-1;
 38     }
 39     dis[s]=0;
 40     vis[s]=true;
 41     q.push(s);
 42     while (!q.empty()){
 43         int u = q.front();
 44         q.pop();
 45         vis[u]=false;
 46         for(int i=head[u];i!=-1;i=edge[i].next){
 47             int v = edge[i].to;
 48             if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
 49                 dis[v]=dis[u]+edge[i].cost;
 50                 pre[v]=i;
 51                 if(!vis[v]){
 52                     vis[v]=true;
 53                     q.push(v);
 54                 }
 55             }
 56         }
 57     }
 58     if(pre[t]==-1)return false;
 59     return true;
 60 }
 61 int minCostMaxFlow(int s,int t,int &cost){
 62     int flow = 0;
 63     cost = 0;
 64     while (spfa(s,t)){
 65         int Min = INF;
 66         for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
 67             //从最后一个点，向前遍历取最小值
 68             if(Min>edge[i].cap-edge[i].flow)
 69                 Min = edge[i].cap-edge[i].flow;
 70         }
 71         for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
 72             edge[i].flow+=Min;
 73             edge[i^1].flow-=Min;
 74             cost+=edge[i].cost*Min;
 75         }
 76         flow+=Min;
 77     }
 78     return flow;
 79 }
 80 int main(){
 81     ios::sync_with_stdio(false);
 82     int n;
 83     int a[105];
 84     int sum = 0;
 85     cin>>n;
 86     for(int i=1;i<=n;i++) {
 87         cin >> a[i];
 88         sum+=a[i];
 89     }
 90     sum/=n;
 91     init(n+2);
 92     for(int i=1;i<=n;i++){
 93         if(a[i]>sum){
 94             addEdge(0,i,a[i]-sum,0);
 95         } else if(a[i]<sum){
 96             addEdge(i,n+1,sum-a[i],0);
 97         }
 98         if(i!=n){
 99             addEdge(i,i+1,INF,1);
100             addEdge(i+1,i,INF,1);
101         } else{
102             addEdge(i,1,INF,1);
103             addEdge(1,i,INF,1);
104         }
105     }
106     int ans = 0;
107     minCostMaxFlow(0,n+1,ans);
108     cout<<ans<<endl;
109 }

View Code

3.P4015 运输问题

费用流，全裸的吧，啊啊啊什么全裸？？

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 const int MAXN = 10000;
  5 const int MAXM = 100000;
  6 const int INF = 0x3f3f3f3f;
  7 int n,m;
  8 struct Edge{
  9     int to,next,cap,flow,cost;
 10 }edge[MAXM];
 11 int head[MAXN],tol;
 12 int pre[MAXN],dis[MAXN];
 13 bool vis[MAXN];
 14 void init(){
 15     tol = 0;
 16     memset(head,-1, sizeof(head));
 17 }
 18 void addEdge(int u,int v,int cap,int cost){
 19     edge[tol].to=v;
 20     edge[tol].cap = cap;
 21     edge[tol].cost = cost;
 22     edge[tol].flow = 0;
 23     edge[tol].next = head[u];
 24     head[u]=tol++;
 25     edge[tol].to = u;
 26     edge[tol].cap = 0;
 27     edge[tol].cost = -cost;
 28     edge[tol].flow = 0;
 29     edge[tol].next = head[v];
 30     head[v]=tol++;
 31 }
 32 bool spfa(int s,int t,int N){
 33     queue<int> q;
 34     for(int i=0;i<N;i++){
 35         dis[i]=INF;
 36         vis[i] = false;
 37         pre[i]=-1;
 38     }
 39     dis[s]=0;
 40     vis[s]=true;
 41     q.push(s);
 42     while (!q.empty()){
 43         int u = q.front();
 44         q.pop();
 45         vis[u] = false;
 46         for(int i=head[u];i!=-1;i=edge[i].next){
 47             int v = edge[i].to;
 48             if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
 49                 dis[v]=dis[u]+edge[i].cost;
 50                 pre[v]=i;
 51                 if(!vis[v]){
 52                     vis[v]=true;
 53                     q.push(v);
 54                 }
 55             }
 56         }
 57     }
 58     if(pre[t]==-1)return false;
 59     return true;
 60 }
 61 ll minCostMaxFlow(int s,int t,ll &cost,int N){
 62     int flow = 0;
 63     cost = 0;
 64     while (spfa(s,t,N)){
 65         int Min = INF;
 66         for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
 67             if(Min>edge[i].cap-edge[i].flow)
 68                 Min = edge[i].cap-edge[i].flow;
 69         }
 70         for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
 71             edge[i].flow+=Min;
 72             edge[i^1].flow-=Min;
 73             cost+=1ll*edge[i].cost*Min;
 74         }
 75     }
 76     return flow;
 77 }
 78 
 79 int a[105],b[105],g[105][105];
 80 int main(){
 81     init();
 82     ios::sync_with_stdio(false);
 83     cin>>n>>m;
 84     for(int i=1;i<=n;i++){
 85         cin>>a[i];
 86         addEdge(0,i,a[i],0);
 87     }
 88     for(int i=1;i<=m;i++){
 89         cin>>b[i];
 90         addEdge(i+n,n+m+1,b[i],0);
 91     }
 92     for(int i=1;i<=n;i++){
 93         for(int j=1;j<=m;j++){
 94             cin>>g[i][j];
 95             addEdge(i,j+n,INF,g[i][j]);
 96         }
 97     }
 98     ll cost = 0;
 99     minCostMaxFlow(0,n+m+1,cost,n+m+2);
100     cout<<cost<<endl;
101     cost = 0;
102     init();
103     for(int i=1;i<=n;i++){
104         addEdge(0,i,a[i],0);
105     }
106     for(int i=1;i<=m;i++){
107         addEdge(i+n,n+m+1,b[i],0);
108     }
109     for(int i=1;i<=n;i++){
110         for(int j=1;j<=m;j++){
111             addEdge(i,j+n,INF,-g[i][j]);
112         }
113     }
114     minCostMaxFlow(0,n+m+1,cost,n+m+2);
115     cout<<-cost<<endl;
116 }

View Code

4. 4014 分配问题

费用流&二分图完美匹配，只写了费用流的做法，这道题建图也很显然吧。。。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 const int MAXN = 10000;
  5 const int MAXM = 100000;
  6 const int INF = 0x3f3f3f3f;
  7 struct Edge{
  8     int to,next,cap,flow,cost;
  9 }edge[MAXM];
 10 int head[MAXN],tol;
 11 int pre[MAXN],dis[MAXN];
 12 bool vis[MAXN];
 13 void init(){
 14     tol = 0;
 15     memset(head,-1, sizeof(head));
 16 }
 17 void addEdge(int u,int v,int cap,int cost){
 18     edge[tol].to=v;
 19     edge[tol].cap = cap;
 20     edge[tol].cost = cost;
 21     edge[tol].flow = 0;
 22     edge[tol].next = head[u];
 23     head[u]=tol++;
 24     edge[tol].to = u;
 25     edge[tol].cap = 0;
 26     edge[tol].cost = -cost;
 27     edge[tol].flow = 0;
 28     edge[tol].next = head[v];
 29     head[v]=tol++;
 30 }
 31 bool spfa(int s,int t,int N){
 32     queue<int> q;
 33     for(int i=0;i<N;i++){
 34         dis[i]=INF;
 35         vis[i] = false;
 36         pre[i]=-1;
 37     }
 38     dis[s]=0;
 39     vis[s]=true;
 40     q.push(s);
 41     while (!q.empty()){
 42         int u = q.front();
 43         q.pop();
 44         vis[u] = false;
 45         for(int i=head[u];i!=-1;i=edge[i].next){
 46             int v = edge[i].to;
 47             if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
 48                 dis[v]=dis[u]+edge[i].cost;
 49                 pre[v]=i;
 50                 if(!vis[v]){
 51                     vis[v]=true;
 52                     q.push(v);
 53                 }
 54             }
 55         }
 56     }
 57     if(pre[t]==-1)return false;
 58     return true;
 59 }
 60 ll minCostMaxFlow(int s,int t,ll &cost,int N){
 61     int flow = 0;
 62     cost = 0;
 63     while (spfa(s,t,N)){
 64         int Min = INF;
 65         for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
 66             if(Min>edge[i].cap-edge[i].flow)
 67                 Min = edge[i].cap-edge[i].flow;
 68         }
 69         for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
 70             edge[i].flow+=Min;
 71             edge[i^1].flow-=Min;
 72             cost+=1ll*edge[i].cost*Min;
 73         }
 74     }
 75     return flow;
 76 }
 77 int n;
 78 int g[105][105];
 79 int main(){
 80     ios::sync_with_stdio(false);
 81     init();
 82     cin>>n;
 83     for(int i=1;i<=n;i++){
 84         addEdge(0,i,1,0);
 85         for(int j=1;j<=n;j++){
 86             cin>>g[i][j];
 87             addEdge(i,j+n,1,g[i][j]);
 88         }
 89         addEdge(i+n,n+n+1,1,0);
 90     }
 91     ll cost = 0;
 92     minCostMaxFlow(0,n+n+1,cost,n+n+2);
 93     cout<<cost<<endl;
 94     init();
 95     cost=0;
 96     for(int i=1;i<=n;i++){
 97         addEdge(0,i,1,0);
 98         for(int j=1;j<=n;j++){
 99             addEdge(i,j+n,1,-g[i][j]);
100         }
101         addEdge(i+n,n+n+1,1,0);
102     }
103     minCostMaxFlow(0,n+n+1,cost,n+n+2);
104     cout<<-cost<<endl;
105 }

View Code

5. 3254 圆桌问题

最大流，源点到每个单位连人数，每个单位到每个桌子连1，每个桌子到汇点连人数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 425
 4 #define INF 0x3f3f3f3f
 5 
 6 int e[N][N];
 7 int pre[N]; //记录当前点的前驱。
 8 int d[N];   //记录距离标号  i-t距离的下界。
 9 int num[N];  //gap优化，每个距离下标下的节点编号有多少个，为0的话，说明s-t不连通
10 int SAP(int s,int t){
11     memset(pre,-1,sizeof(pre));
12     memset(d,0,sizeof(d));
13     memset(num,0,sizeof(num));
14     num[0]=t;
15     int v,u=pre[s]=s,flow=0,aug=INF;
16     while(d[s]<t){  //else 残量网络中不存在s-t路。
17         //寻找可行弧
18         for(v=1;v<=t;v++){
19             if(e[u][v]>0&&d[u]==d[v]+1){
20                 break;
21             }
22         }
23         if(v<=t){
24             pre[v]=u;
25             u=v;
26             if(v==t){
27                 aug=INF;
28                 //寻找当前找到路径上的最大流
29                 for(int i=v;i!=s;i=pre[i]){
30                     if(aug>e[pre[i]][i]) aug=e[pre[i]][i];
31                 }
32                 flow+=aug;
33                 //更新残留网络。
34                 for(int i=v;i!=s;i=pre[i]){
35                     e[pre[i]][i]-=aug;
36                     e[i][pre[i]]+=aug;
37                 }
38                 u=s;        //从源点开始继续搜。
39             }
40         }else{
41             //找不到可行弧
42             int minlevel=t;
43             //寻找与当前点连接的最小的距离标号。
44             for(v=1;v<=t;v++){
45                 if(e[u][v]>0&&minlevel>d[v]){
46                     minlevel=d[v];
47                 }
48             }
49             num[d[u]]--;            //当前标号的数目减一
50             if(!num[d[u]]) break; //出现断层。
51             d[u]=minlevel+1;
52             num[d[u]]++;
53             u=pre[u];
54         }
55     }
56     return flow;
57 }
58 int n,m;
59 int a[303],b[303];
60 int main() {
61     ios::sync_with_stdio(false);
62     cin>>n>>m;
63     int sum = 0;
64     for(int i=1;i<=n;i++){
65         cin>>a[i];
66         sum+=a[i];
67     }
68     for(int i=1;i<=m;i++){
69         cin>>b[i];
70     }
71     for(int i=2;i<=n+1;i++){
72         for(int j=1;j<=m;j++){
73             e[i][j+n+1]=1;
74         }
75     }
76     for(int i=2;i<=n+1;i++){
77         e[1][i] = a[i-1];
78     }
79     for(int i=1;i<=m;i++){
80         e[i+n+1][n+m+2]=b[i];
81     }
82     int flag = SAP(1,n+m+2)==sum;
83     cout<<flag<<endl;
84     if(flag){
85         for(int i=2;i<=n+1;i++){
86             for(int j=1;j<=m;j++){
87                 if(e[i][j+n+1]==0){
88                     cout<<j<<' ';
89                 }
90             }
91             cout<<endl;
92         }
93     }
94 }

View Code

6.2774 方格取数

很显然的最小割，用所有数的和减去最小割就是答案了吧，然后最小割等于最大流。

我们可以把点按照 (i+j) 的奇偶分为两类，然后两类之间连边INF，源点到一类点连边权值，另一类到汇点连边权值。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int INF = 0x3f3f3f3f;
 4 struct Edge{
 5     int from,to,cap,flow;//容量流量
 6 };
 7 int n,m,s,t;//节点数，边数，源汇点
 8 vector<Edge> edges;//边表
 9 vector<int> G[35555];//G[i][j]表示结点i的第j条边在e数组中的序号
10 bool vis[36666];//BFS使用
11 int d[35555];//分层图
12 int cur[35555];//当前弧
13 void addEdge(int from,int to,int cap){
14     edges.push_back((Edge){from,to,cap,0});
15     edges.push_back(Edge{to,from,0,0});
16     m = edges.size();
17     G[from].push_back(m-2);
18     G[to].push_back(m-1);
19 }
20 bool BFS(){
21     memset(vis,0, sizeof(vis));
22     queue<int> Q;
23     Q.push(s);
24     d[s]=0;
25     vis[s]=1;
26     while (!Q.empty()){
27         int x = Q.front();
28         Q.pop();
29         for(int i=0;i<G[x].size();i++){
30             Edge &e = edges[G[x][i]];
31             if(!vis[e.to]&&e.cap>e.flow){
32                 vis[e.to]=1;
33                 d[e.to]=d[x]+1;
34                 Q.push(e.to);
35             }
36         }
37     }
38     return vis[t];//能否增广到
39 }
40 int DFS(int x,int a){
41     if(x==t||a==0)
42         return a;
43     int flow = 0,f;
44     for(int& i=cur[x];i<G[x].size();i++){//当前弧优化
45         Edge& e = edges[G[x][i]];
46         if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){
47             e.flow+=f;
48             edges[G[x][i]^1].flow-=f;
49             flow+=f;
50             a-=f;
51             if(a==0)//??????炸点优化o.o
52                 break;
53         }
54     }
55     return flow;
56 }
57 int maxflow(){
58     int flow = 0;
59     while (BFS()){
60         memset(cur,0, sizeof(cur));
61         flow+=DFS(s,INF);
62     }
63     return flow;
64 }
65 int M,N,g[105][105];
66 bool in(int x,int y){
67     return x>=1&&x<=M&&y>=1&&y<=N;
68 }
69 int main(){
70     ios::sync_with_stdio(false);
71     cin>>M>>N;
72     int sum = 0;
73     for(int i=1;i<=M;i++){
74         for(int j=1;j<=N;j++){
75             cin>>g[i][j];
76             sum+=g[i][j];
77         }
78     }
79     for(int i=1;i<=M;i++){
80         for(int j=1;j<=N;j++){
81             if((i+j)&1){
82                 addEdge(0,(i-1)*N+j,g[i][j]);
83                 if(in(i-1,j))
84                     addEdge((i-1)*N+j,(i-2)*N+j,INF);
85                 if(in(i+1,j))
86                     addEdge((i-1)*N+j,i*N+j,INF);
87                 if(in(i,j-1))
88                     addEdge((i-1)*N+j,(i-1)*N+j-1,INF);
89                 if(in(i,j+1))
90                     addEdge((i-1)*N+j,(i-1)*N+j+1,INF);
91             } else{
92                 addEdge((i-1)*N+j,N*M+1,g[i][j]);
93             }
94         }
95     }
96     n=N*M+2,s=0,t=N*M+1;
97     cout<<sum-maxflow()<<endl;
98 }

View Code

7. 2763 试题库问题

这道题非常的水啊，我刚才写了写一遍就过了。

最大流，建图请看代码qwq

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int MAXN = 2010;
  4 const int MAXM = 66666;
  5 const int INF = 0x3f3f3f3f;
  6 struct Edge{
  7     int to,next,cap,flow;
  8 }edge[MAXM];
  9 int tol;
 10 int head[MAXN];
 11 void init(){
 12     tol = 2;
 13     memset(head,-1, sizeof(head));
 14 }
 15 void addEdge(int u,int v,int w,int rw = 0){
 16     edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0;
 17     edge[tol].next=head[u];head[u]=tol++;
 18     edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=0;
 19     edge[tol].next=head[v];head[v]=tol++;
 20 }
 21 int Q[MAXN];
 22 int dep[MAXN],cur[MAXN],sta[MAXN];
 23 bool bfs(int s,int t,int n){
 24     int front = 0,tail = 0;
 25     memset(dep,-1, sizeof(dep[0])*(n+1));
 26     dep[s]=0;
 27     Q[tail++] = s;
 28     while (front<tail){
 29         int u = Q[front++];
 30         for(int i=head[u];i!=-1;i=edge[i].next){
 31             int v = edge[i].to;
 32             if(edge[i].cap>edge[i].flow&&dep[v]==-1){
 33                 dep[v]=dep[u]+1;
 34                 if(v==t)return true;
 35                 Q[tail++] = v;
 36             }
 37         }
 38     }
 39     return false ;
 40 }
 41 int dinic(int s,int t,int n){
 42     int maxflow = 0;
 43     while (bfs(s,t,n)){
 44         for(int i=0;i<n;i++)cur[i] = head[i];
 45         int u = s,tail = 0;
 46         while (cur[s]!=-1){
 47             if(u==t){
 48                 int tp = INF;
 49                 for(int i=tail-1;i>=0;i--){
 50                     tp = min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
 51                 }
 52                 maxflow +=tp;
 53                 for(int i=tail-1;i>=0;i--){
 54                     edge[sta[i]].flow+=tp;
 55                     edge[sta[i]^1].flow-=tp;
 56                     if(edge[sta[i]].cap-edge[sta[i]].flow==0)
 57                         tail = i;
 58                 }
 59                 u=edge[sta[tail]^1].to;
 60             }
 61             else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
 62                 sta[tail++]=cur[u];
 63                 u = edge[cur[u]].to;
 64             }
 65             else{
 66                 while (u!=s&&cur[u]==-1)
 67                     u = edge[sta[--tail]^1].to;
 68                 cur[u] = edge[cur[u]].next;
 69             }
 70         }
 71     }
 72     return maxflow;
 73 }
 74 int k,n,a,b,sum;
 75 int main(){
 76     ios::sync_with_stdio(false);
 77     init();
 78     cin>>k>>n;
 79     for(int i=1;i<=k;i++){
 80         cin>>a;
 81         sum+=a;
 82         addEdge(i+n,k+n+1,a);
 83     }
 84     for(int i=1;i<=n;i++){
 85         addEdge(0,i,1);
 86         cin>>a;
 87         while (a--){
 88            cin>>b;
 89            //v[i].push_back(b);
 90            addEdge(i,b+n,1);
 91         }
 92     }
 93     int ans = dinic(0,k+n+1,k+n+2);
 94     if(ans!=sum){
 95         cout<<"No Solution!"<<endl;
 96     } else{
 97         for(int i=1;i<=k;i++){
 98             cout<<i<<": ";
 99             int tmp = i+n;
100             for(int j=head[tmp];j!=-1;j=edge[j].next){
101                 if(edge[j^1].flow==1)
102                     cout<<edge[j].to<<' ';
103             }
104             cout<<endl;
105         }
106     }
107 }

View Code

8. 2764 最小路径覆盖问题

拆点就行，然后跑二分图匹配&最大流，每匹配到一个就意味着有两个点可以连在一条边上吧，所以答案就是总的减去匹配数，详细的可以去看hzw的blog，顺便%hzw

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,m,a,b;
 4 const int MAXN= 305;
 5 int g[MAXN][MAXN];
 6 int linker[MAXN],used[MAXN];
 7 int vis[MAXN];
 8 vector<int> ans;
 9 bool dfs(int u){
10     for (int v = 1;v<=2*n;v++){
11         if(g[u][v]&&!used[v]) {
12             used[v] = true;
13             if (linker[v] == -1 || dfs(linker[v])) {
14                 linker[v] = u;
15                 return true;
16             }
17         }
18     }
19     return false;
20 }
21 int hungary(){
22     int res = 0;
23     memset(linker,-1, sizeof(linker));
24     for(int u=1;u<=n;u++){
25         memset(used,0, sizeof(used));
26         if (dfs(u))
27             res++;
28     }
29     return res;
30 }
31 int main(){
32     ios::sync_with_stdio(false);
33     cin>>n>>m;
34     while (m--){
35         cin>>a>>b;
36         g[a][b+n]=1;
37     }
38     int res = hungary();
39     for(int i=2*n;i>n;i--){
40         //cout<<linker[i]<<' ';
41         if(vis[i])
42             continue;
43         int tmp = i;
44         while (tmp!=n-1){
45             ans.push_back(tmp-n);
46             tmp=linker[tmp]+n;
47             vis[tmp]=1;
48         }
49         reverse(ans.begin(),ans.end());
50         for(int j=0;j<ans.size();j++)
51             cout<<ans[j]<<' ';
52         cout<<endl;
53         ans.clear();
54     }
55     cout<<n-res<<endl;
56 }

View Code

9.牛客国庆day6A题(乱入

大水题，题解说的什么乱七八咋的(逃

一共n+m+2个点就可以，然后连边就是13579这样子。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 const int MAXN = 10000;
  5 const int MAXM = 100000;
  6 const int INF = 0x3f3f3f3f;
  7 struct Edge{
  8     int to,next,cap,flow,cost;
  9 }edge[MAXM];
 10 int head[MAXN],tol;
 11 int pre[MAXN],dis[MAXN];
 12 bool vis[MAXN];
 13 void init(){
 14     tol = 0;
 15     memset(head,-1, sizeof(head));
 16 }
 17 void addEdge(int u,int v,int cap,int cost){
 18     edge[tol].to=v;
 19     edge[tol].cap = cap;
 20     edge[tol].cost = cost;
 21     edge[tol].flow = 0;
 22     edge[tol].next = head[u];
 23     head[u]=tol++;
 24     edge[tol].to = u;
 25     edge[tol].cap = 0;
 26     edge[tol].cost = -cost;
 27     edge[tol].flow = 0;
 28     edge[tol].next = head[v];
 29     head[v]=tol++;
 30 }
 31 bool spfa(int s,int t,int N){
 32     queue<int> q;
 33     for(int i=0;i<N;i++){
 34         dis[i]=INF;
 35         vis[i] = false;
 36         pre[i]=-1;
 37     }
 38     dis[s]=0;
 39     vis[s]=true;
 40     q.push(s);
 41     while (!q.empty()){
 42         int u = q.front();
 43         q.pop();
 44         vis[u] = false;
 45         for(int i=head[u];i!=-1;i=edge[i].next){
 46             int v = edge[i].to;
 47             if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
 48                 dis[v]=dis[u]+edge[i].cost;
 49                 pre[v]=i;
 50                 if(!vis[v]){
 51                     vis[v]=true;
 52                     q.push(v);
 53                 }
 54             }
 55         }
 56     }
 57     if(pre[t]==-1)return false;
 58     return true;
 59 }
 60 ll minCostMaxFlow(int s,int t,ll &cost,int N){
 61     int flow = 0;
 62     cost = 0;
 63     while (spfa(s,t,N)){
 64         int Min = INF;
 65         for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
 66             if(Min>edge[i].cap-edge[i].flow)
 67                 Min = edge[i].cap-edge[i].flow;
 68         }
 69         for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
 70             edge[i].flow+=Min;
 71             edge[i^1].flow-=Min;
 72             cost+=1ll*edge[i].cost*Min;
 73         }
 74         flow+=Min;
 75     }
 76     return flow;
 77 }
 78 int n,m;
 79 int main(){
 80     ios::sync_with_stdio(false);
 81     init();
 82     cin>>n>>m;
 83     int a,b;
 84     for(int i=1;i<=n;i++){
 85         cin>>a>>b;
 86         addEdge(i,a+n,1,0);
 87         addEdge(i,b+n,1,0);
 88     }
 89     for(int i=1;i<=n;i++){
 90         addEdge(0,i,1,0);
 91     }
 92     for(int i=n+1;i<=n+m;i++){
 93         for(int j=1;j<=n;j++){
 94             addEdge(i,n+m+1,1,2*j-1);
 95         }
 96     }
 97     ll cost = 0;
 98     minCostMaxFlow(0,n+m+1,cost,n+m+2);
 99     cout<<cost<<endl;
100 }

View Code

唔然后剩下的全咕着，应该要等这个赛季结束之后，顺便我去的北京，祝自己rp++；