最大流笔记

概念

求两点间的路径中可在同一时间内通过的最大量

EK算法

通过bfs找通路，找到后回溯；

每确定一条边时，同时建立一天反方向的边以用来进行反悔操作（毕竟一次性找到正确方案的概率太低了）

code

#include<bits/stdc++.h>
#define ll long long
#define inl inline
#define re register
using namespace std;
inl int read() {int sum=0,f=1;char c=getchar();while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}return sum*f;
}
const int N=210;
int dis[10000010],ans,head[N<<1],tot=1,n,m,f[210][210];
struct node{int to,w,nxt;
}e[10000010];
inl void add(int u,int v,int w) {e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;e[++tot].to=u;e[tot].w=0;e[tot].nxt=head[v];head[v]=tot;
}
bool vis[210];
int pre[N];
inl bool bfs() {memset(vis,0,sizeof(vis));queue<int> q;dis[1]=100000000;vis[1]=1;q.push(1);while(!q.empty()) {int u=q.front();q.pop();for(re int i=head[u];i;i=e[i].nxt) {int v=e[i].to;if(vis[v]==1 || e[i].w==0) continue;dis[v]=min(dis[u],e[i].w) ;//cout<<dis[v]<<endl;pre[v]=i;q.push(v);vis[v]=1;if(v==n) return 1;}}return 0;
}
inl void update() {int u=n;while(u!=1) {int v=pre[u] ;e[v].w-=dis[n];e[v^1].w+=dis[n];u=e[v^1].to;}ans+=dis[n];
}
int main() {m=read(),n=read();for(re int i=1;i<=m;i++) {int u=read(),v=read(),w=read();if(!f[u][v]) {add(u,v,w);f[u][v]=tot;}else{e[f[u][v]-1].w+=w;}}while(bfs()) {//cout<<dis[n]<<endl;update();}cout<<ans<<endl;return 0;
}

Dinic算法

也是运用bfs将原图进行分层，但统计答案时使用dfs,，可大大降低时间复杂度

code

#include<bits/stdc++.h>
#define ll long long
#define re register
#define inl inline
using namespace std;
inl int read() {int sum=0,f=1;char c=getchar();while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {sum=(sum<<3)+(sum<<1)+(c^48);c=getchar();}return sum*f;
}
const int N=210;
int n,m,x,head[N<<1],f[210][210],tot=1,cur[N*N],ans,d[N];
struct node{int to,nxt,w;
}e[N*N+1000];
inl void add(int u,int v,int w) {//cout<<1<<endl;e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;e[++tot].to=u;e[tot].w=0;e[tot].nxt=head[v];head[v]=tot;
}
inl bool bfs() {memset(d,0,sizeof(d));queue<int> q;d[1]=1;q.push(1);while(!q.empty()) {int u=q.front() ;q.pop();for(re int i=head[u];i;i=e[i].nxt) {int v=e[i].to;if(!d[v] && e[i].w) {d[v]=d[u]+1;q.push(v);if(v==n) return 1;}}}return 0;
}
inl int dfs(int u,int mf) {if(u==n) return mf;int tmp=0;for(int i=cur[u];i;i=e[i].nxt) {cur[u]=i;int v=e[i].to;if(d[v]==d[u]+1 && e[i].w) {int tmp1=dfs(v,min(mf,e[i].w));e[i].w-=tmp1;e[i^1].w+=tmp1;tmp+=tmp1;mf-=tmp1;if(!mf) break;}}if(!tmp) d[u]=0;return tmp;
}
inl void dinic() {while(bfs()) {memcpy(cur,head,sizeof head);ans+=dfs(1,100000000);}
}
int main() {n=read();m=read();x=read();//cout<<n<<" "<<m<<" "<<x<<endl;for(re int i=1;i<=m;i++) {int u=read(),v=read(),w=read();if(!f[u][v]) {add(u,v,w);f[u][v]=tot;}else{e[f[u][v]-1].w+=w;}}dinic();if(!ans) {puts("Orz Ni Jinan Saint Cow!");}else {int p=x/ans;if(p*ans<x) {p++;}printf("%d %d\n",ans,p);}return 0;
}