网络流

dinic

#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int maxn = 1e5+10;const int inf = 0x3f3f3f3f;int n,m,s,t,tol,head[maxn],dep[maxn],x[50][50];struct Edge{int v,w,nxt;}E[maxn];void add_edge(int u,int v,int w){E[tol] = Edge{v,w,head[u]};head[u] = tol++;}void insert(int u, int v, int c){add_edge(u, v, c);add_edge(v, u, 0);}bool Bfs(){memset(dep,0, sizeof(dep));queue<int>q;while(!q.empty())q.pop();q.push(s);dep[s] = 1;while(!q.empty()){int u = q.front();q.pop();for(int i = head[u];i != -1;i = E[i].nxt){if(E[i].w && !dep[E[i].v]){dep[E[i].v] = dep[u] + 1;q.push(E[i].v);if(E[i].v == t)return true;}}}return false;}int Dfs(int u,int f){if(u == t)return f;int used = 0,d = 0;for(int i = head[u];i != -1;i = E[i].nxt){if(dep[u] == dep[E[i].v] - 1 && E[i].w){if((d = Dfs(E[i].v,min(f - used,E[i].w)))){used += d;E[i].w -= d;E[i^1].w += d;}}}if(!used)dep[u] = 0;return used;}int Dinic(){int max_flow = 0,d;while(Bfs()){while((d = Dfs(s,inf)))max_flow += d;}return max_flow;}int main(){memset(head,-1,sizeof(head));scanf(\"%lld%lld\",&m,&n);int s=0,t=m*n+1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){int u,v,c;scanf(\"%d%d%d\",&u,&v,&c);insert(u,v,c);}}return 0;}

EK算法

#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int maxn=5003;const int inf=0x7fffffff;int r[maxn][maxn],m[maxn][maxn];bool visit[maxn];int pre[maxn];int m,n;bool bfs(int s,int t){int p;queue<int> q;memset(pre,-1,sizeof(pre));memset(visit,false,sizeof(visit));pre[s]=s;visit[s]=true;q.push(s);while(!q.empty()){p=q.front();q.pop();for(int i=1;i<=n;i++){if(r
[i]>0&&!visit[i]){pre[i]=p;visit[i]=true;if(i==t)return true;q.push(i);}}}return false;}int EdmondsKarp(int s,int t){int flow=0,d,i;while(bfs(s,t)){d=inf;for(i=t;i!=s;i=pre[i])d=d<r[pre[i]][i]? d:r[pre[i]][i];for(i=t;i!=s;i=pre[i]){r[pre[i]][i]-=d;r[i][pre[i]]+=d;}flow+=d;}return flow;}int main(){int s,t;scanf(\"%d%d%d%d\",&n,&m,&s,&t);int u,v,w,f;memset(r,0,sizeof(r));for(int i=0;i<m;i++){scanf(\"%d%d%d%d\",&u,&v,&w,&f);r[u][v]+=w;m[u][v]+=f;}printf(\"%d\\n\",EdmondsKarp(1,n));return 0;}

EK+边表

#include <iostream>#include<cstring>#include<cstdio>using namespace std;#define INF 0x3f3f3f#define maxm 200005#define maxn 10005struct qi{int st,en,num;}flow[maxm];int n, m,pre[maxn],re[maxn][maxn/10],num[maxn],st,en;int q[maxn], curr_pos, st_pos, end_pos, ne, max_flow;bool wh[maxn];int input;char a;bool Bfs(int st, int en){int i, j;st_pos = -1, end_pos = 0;memset(wh, 0, sizeof wh);wh[st] = 1;q[0] = st;while(st_pos != end_pos){curr_pos = q[++st_pos];for(i = 0; i < num[curr_pos]+1; ++i){j = re[curr_pos][i];if(flow[j].st == curr_pos && flow[j].num > 0 && !wh[flow[j].en]){ne = flow[j].en;wh[ne] = 1;pre[ne] = j;q[++end_pos] = flow[j].en;if(ne == en)return true;}}}return false;}int EK(int start_pos, int end_pos){int i, minn;while(Bfs(start_pos, end_pos)){minn = INF;for(i = end_pos; i != st; i = flow[pre[i]].st){minn = min(minn, flow[pre[i]].num);}for(i = end_pos; i != st; i = flow[pre[i]].st){flow[pre[i]].num -= minn;flow[pre[i]+m].num += minn;}max_flow += minn;}return max_flow;}int main(){scanf(\"%d%d%d%d\",&n,&m,&st,&en);int u,v,w;for(int i = 0; i != m; ++i){scanf(\"%d%d%d\",&u,&v,&w);flow[i].st = u;flow[i].en = v;flow[i].num = w;re[flow[i].st][++num[flow[i].st]] = i;re[flow[i].en][++num[flow[i].en]] = i+m;}for(int i = m; i != 2*m; ++i){flow[i].st = flow[i-m].en;flow[i].en = flow[i-m].st;}printf(\"%d\", EK(st,en));}

最大流最小费用

#include<cstdio>#include<cstring>#include<queue>#define Pair pair<int,int>#define fi first#define se second#define AddEdge(x,y,f,z) add_edge(x,y,f,z);add_edge(y,x,0,-z);char buf[1<<20],*p1=buf,*p2=buf;using namespace std;const int MAXN=1e6+1,INF=1e8+10;int N,M,S,T;struct node{int u,v,f,w,nxt;}edge[MAXN];int head[MAXN],num=2;inline void add_edge(int x,int y,int f,int z){edge[num].u=x;edge[num].v=y;edge[num].f=f;edge[num].w=z;edge[num].nxt=head[x];head[x]=num++;}int h[MAXN],dis[MAXN],PrePoint[MAXN],PreEdge[MAXN];Pair Dij(){int ansflow=0,anscost=0;while(1){priority_queue<Pair>q;memset(dis,0xf,sizeof(dis));dis[S]=0;q.push(make_pair(0,S));while(q.size()!=0){Pair p=q.top();q.pop();if(-p.fi!=dis[p.se]) continue;if(p.se==T) break;for(int i=head[p.se];i!=-1;i=edge[i].nxt){int nowcost=edge[i].w+h[p.se]-h[edge[i].v];if(edge[i].f>0&&dis[edge[i].v]>dis[p.se]+nowcost){dis[edge[i].v]=dis[p.se]+nowcost;q.push(make_pair(-dis[edge[i].v],edge[i].v));PrePoint[edge[i].v]=p.se;PreEdge[edge[i].v]=i;}}}if(dis[T]>INF) break;for(int i=0;i<=N;i++) h[i]+=dis[i];int nowflow=INF;for(int now=T;now!=S;now=PrePoint[now])nowflow=min(nowflow,edge[PreEdge[now]].f);for(int now=T;now!=S;now=PrePoint[now])edge[PreEdge[now]].f-=nowflow,edge[PreEdge[now]^1].f+=nowflow;ansflow+=nowflow;anscost+=nowflow*h[T];}return make_pair(ansflow,anscost);}int main(){memset(head,-1,sizeof(head));scanf(\"%d%d%d%d\",&N,&M,&S,&T);for(int i=1;i<=M;i++){int x,y,f,z;scanf(\"%d%d%d%d\",&x,&y,&f,&z);AddEdge(x,y,f,z);}Pair ans=Dij();printf(\"%d %d\",ans.fi,ans.se);return 0;}

二分图

匈牙利算法

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn=107;int m,n;int t[maxn][maxn];bool vis[maxn];int match[maxn];bool dfs(int u){for(int v=1;v<=n;v++){if(t[u][v]&&!vis[v]){vis[v]=1;if(match[u]==-1||dfs(match[v])){match[v]=u;return 1;}}}return 0;}int maxmatch(){int ans=0;memset(match,-1,sizeof(match));for(int i=1;i<=m;i++){memset(vis,false,sizeof(vis));ans+=dfs(i);}return ans;}int main(){int T,num,ans;scanf(\"%d%d\",&n,&m);for(int i=1;i<=m;i++){scanf(\"%d\",&T);for(int j=1;j<=T;j++){scanf(\"%d\",&num);t[i][num]=1;}}ans=maxmatch();printf(\"%d\",ans);}

[p]实例：过山车问题

#include<stdio.h>#include<string.h>int line[510][510],boy[510],used[510];int n,m;int Find(int x){int i,j;for(i=1;i<=m;i++)//遍历所有被选者{if(line[x][i]==1&&used[i]==0){//如果 x对i有好感且在这一个递归选取阶段没有被选取（哪怕是暂时选取，新的递归可能会换）used[i]=1;//标记被选取if(boy[i]==0||Find(boy[i]))//如果被选者没有归属或他的归属着可以调换（他的归属者可以选择其它被选者）{boy[i]=x;//将归属定为 xreturn 1;}}}return 0;}int main(){int i,j,k,x,y,sum;while(~scanf(\"%d\",&n,&m)){memset(line,0,sizeof(line));memset(boy,0,sizeof(boy));memset(used,0,sizeof(used));for(i=0;i<k;i++){scanf(\"%d %d\",&x,&y);line[x][y]=1;//表示 x希望与 y有关系}sum=0;//记录能撮合的情侣对数for(i=1;i<=n;i++){memset(used,0,sizeof(used));//每次都要清 0if(Find(i)) sum++;//找到一对就记录}printf(\"%d\\n\",sum);}return 0;}

KN算法

#include <stdio.h>#include <string.h>#define M 310#define inf 0x3f3f3f3fint n,nx,ny;int link[M],lx[M],ly[M],slack[M];    //lx,ly为顶标，nx,ny分别为x点集y点集的个数int visx[M],visy[M],w[M][M];int DFS(int x){visx[x] = 1;for (int y = 1;y <= ny;y ++){if (visy[y])continue;int t = lx[x] + ly[y] - w[x][y];if (t == 0)       //{visy[y] = 1;if (link[y] == -1||DFS(link[y])){link[y] = x;return 1;}}else if (slack[y] > t)  //不在相等子图中slack 取最小的slack[y] = t;}return 0;}int KM(){int i,j;memset (link,-1,sizeof(link));memset (ly,0,sizeof(ly));for (i = 1;i <= nx;i ++)            //lx初始化为与它关联边中最大的for (j = 1,lx[i] = -inf;j <= ny;j ++)if (w[i][j] > lx[i])lx[i] = w[i][j];for (int x = 1;x <= nx;x ++){for (i = 1;i <= ny;i ++)slack[i] = inf;while (1){memset (visx,0,sizeof(visx));memset (visy,0,sizeof(visy));if (DFS(x))     //若成功（找到了增广轨），则该点增广完成，进入下一个点的增广break;  //若失败（没有找到增广轨），则需要改变一些点的标号，使得图中可行边的数量增加。//方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，//所有在增广轨中的Y方点的标号全部加上一个常数dint d = inf;for (i = 1;i <= ny;i ++)if (!visy[i]&&d > slack[i])d = slack[i];for (i = 1;i <= nx;i ++)if (visx[i])lx[i] -= d;for (i = 1;i <= ny;i ++)  //修改顶标后，要把所有不在交错树中的Y顶点的slack值都减去dif (visy[i])ly[i] += d;elseslack[i] -= d;}}int res = 0;for (i = 1;i <= ny;i ++)if (link[i] > -1)res += w[link[i]][i];return res;}int main (){int i,j;while (scanf (\"%d\",&n)!=EOF){nx = ny = n;//  memset (w,0,sizeof(w));for (i = 1;i <= n;i ++)for (j = 1;j <= n;j ++)scanf (\"%d\",&w[i][j]);int ans = KM();printf (\"%d\\n\",ans);}return 0;}

实例：男女配对

#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int MAXN = 305;const int INF = 0x3f3f3f3f;int love[MAXN][MAXN];   // 记录每个妹子和每个男生的好感度int ex_girl[MAXN];      // 每个妹子的期望值int ex_boy[MAXN];       // 每个男生的期望值bool vis_girl[MAXN];    // 记录每一轮匹配匹配过的女生bool vis_boy[MAXN];     // 记录每一轮匹配匹配过的男生int match[MAXN];        // 记录每个男生匹配到的妹子 如果没有则为-1int slack[MAXN];        // 记录每个汉子如果能被妹子倾心最少还需要多少期望值int N;bool dfs(int girl){vis_girl[girl] = true;for (int boy = 0; boy < N; ++boy) {if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];if (gap == 0) {  // 如果符合要求vis_boy[boy] = true;if (match[boy] == -1 || dfs( match[boy] )) {    // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人match[boy] = girl;return true;}} else {slack[boy] = min(slack[boy], gap);  // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸}}return false;}int KM(){memset(match, -1, sizeof match);    // 初始每个男生都没有匹配的女生memset(ex_boy, 0, sizeof ex_boy);   // 初始每个男生的期望值为0// 每个女生的初始期望值是与她相连的男生最大的好感度for (int i = 0; i < N; ++i) {ex_girl[i] = love[i][0];for (int j = 1; j < N; ++j) {ex_girl[i] = max(ex_girl[i], love[i][j]);}}// 尝试为每一个女生解决归宿问题for (int i = 0; i < N; ++i) {fill(slack, slack + N, INF);    // 因为要取最小值 初始化为无穷大while (1) {// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止// 记录每轮匹配中男生女生是否被尝试匹配过memset(vis_girl, false, sizeof vis_girl);memset(vis_boy, false, sizeof vis_boy);if (dfs(i)) break;  // 找到归宿 退出// 如果不能找到 就降低期望值// 最小可降低的期望值int d = INF;for (int j = 0; j < N; ++j)if (!vis_boy[j]) d = min(d, slack[j]);for (int j = 0; j < N; ++j) {// 所有访问过的女生降低期望值if (vis_girl[j]) ex_girl[j] -= d;// 所有访问过的男生增加期望值if (vis_boy[j]) ex_boy[j] += d;// 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！else slack[j] -= d;}}}// 匹配完成 求出所有配对的好感度的和int res = 0;for (int i = 0; i < N; ++i)res += love[ match[i] ][i];return res;}int main(){while (~scanf(\"%d\", &N)) {for (int i = 0; i < N; ++i)for (int j = 0; j < N; ++j)scanf(\"%d\", &love[i][j]);printf(\"%d\\n\", KM());}return 0;}

二分答案+二分染色

#include <cstdio>#include <cstring>#include <iostream>#include<algorithm>#include<climits>#include<vector>using namespace std;const int maxn=20002;const int inf=0x3f3f3f3f;int m,n,col[maxn];vector<int> ed[maxn];vector<int> len[maxn];bool dfs(int x,int color,int mid){if(col[x]>=0){if(col[x]==color)return true;return false;}col[x]=color;for(int i=0;i<ed[x].size();i++)if(len[x][i]>mid&&!dfs(ed[x][i],1-color,mid))return false;return true;}bool check(int mid){memset(col,-1,sizeof(col));for(int i=1;i<=n;i++)if(col[i]==-1&&!dfs(i,0,mid))return false;return true;}int main(){int ans;scanf(\"%d%d\",&n,&m);for(int i=1;i<=n;i++){ed[i].clear();len[i].clear();}while(m--){int u,v,c;scanf(\"%d%d%d\",&u,&v,&c);ed[u].push_back(v);len[u].push_back(c);ed[v].push_back(u);len[v].push_back(c);}int l=0,r=inf;while(l<r){int mid=(l+r)>>1;if(check(mid))r=mid;elsel=mid+1;}printf(\"%d\\n\",r);}