近日好不容易在自救之路写完暑训遗留下来的网络流8题，在此回顾一下。
Going Home POJ - 2195
题意：m要去H，一个H只能容纳一个m，一步一块钱，问最小花费。
思路：最小费用最大流的板子题。有博客用了Dijkstra，不过在我看来，存在负权边的图是不能使用Dijkstra的，所以虽然我曾立誓再也不写SPFA，现在也不得不屈服了。
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-);
int n,m;
char mp[][];
struct node
{
int x,y;
}p1[maxn],p2[maxn];
int Head[maxn],Next[maxn*maxn],v[maxn*maxn],w[maxn*maxn],cap[maxn*maxn],cnt;
int t1,t2;int ans;
void init()
{
t1=;cnt=t2=ans=;
memset(Head,-,sizeof(Head));
} void add(int x,int y,int z,int f){
// cout<<x<<" "<<y<<" "<<z<<endl;
v[cnt]=y;
w[cnt]=z;
cap[cnt]=f;
Next[cnt]=Head[x];
Head[x]=cnt++; v[cnt]=x;
w[cnt]=-z;
cap[cnt]=;
Next[cnt]=Head[y];
Head[y]=cnt++;
}
bool vis[maxn];
int dis[maxn];
int prevv[maxn],preve[maxn];
int s,t;
bool spfa()
{
queue<int>q;
memset(vis,,sizeof(vis));
for(int i=;i<=t;i++){
dis[i]=inf;
} dis[s]=;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int k=Head[u];k!=-;k=Next[k]){
if(cap[k]&&dis[v[k]]>dis[u]+w[k]){
dis[v[k]]=dis[u]+w[k];
prevv[v[k]]=u;
preve[v[k]]=k; if(!vis[v[k]]){
vis[v[k]]=true;
q.push(v[k]);
}
}
}
}
if(dis[t]==inf){return false;}
else return true;
}
int min_cost_flow()
{
while(spfa()){
for(int i=t;i!=s;i=prevv[i]){
int k=preve[i];
cap[k]-=;
cap[k^]+=;
}
ans+=dis[t];
} } int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){
init();
for(int i=;i<=n;i++){
scanf("%s",mp[i]+);
for(int j=;j<=m;j++){
if(mp[i][j]=='m'){p1[++t1]=node{i,j};}
else if(mp[i][j]=='H'){p2[++t2]=node{i,j};}
}
}
s=;t=t1+t2+;
for(int i=;i<=t1;i++){
add(s,i,,);
for(int j=;j<=t2;j++){
add(i,j+t1,abs(p1[i].x-p2[j].x)+abs(p1[i].y-p2[j].y),inf);
}
}
for(int i=;i<=t2;i++){
add(i+t1,t,,);
} min_cost_flow();
printf("%d\n",ans);
} return ;
}
Dining POJ - 3281
题意：给奶牛做了吃的和喝的，每一头奶牛都只能接受某些吃的和喝的，问最多能满足多少奶牛。
思路：拆点。奶牛只能吃一份也只能和一份，那就把它拆成两点，之间的边容量为一。食物和饮料不用担心，从源点或汇点连边的时候，控制边权为1就可以限制没份食物或饮料只被吃一次了。
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-);
int n,F,D;
int Head[maxn],Next[maxn],v[maxn],w[maxn],cnt;
int s,t;
void init()
{
cnt=;
memset(Head,-,sizeof(Head));
} void add(int x,int y)
{
// cout<<x<<" "<<y<<endl;
v[cnt]=y;
Next[cnt]=Head[x];
w[cnt]=;
Head[x]=cnt++; v[cnt]=x;
Next[cnt]=Head[y];
w[cnt]=;
Head[y]=cnt++;
} int food(int x)
{
return *n++x;
} int drink(int x)
{
return *n++F+x;
} int nu1(int x)
{
return x+;
} int nu2(int x)
{
return x+n+;
} void build()
{
s=;t=drink(D)+;
for(int i=;i<=F;i++){
add(s,food(i));
}
for(int i=;i<=D;i++){
add(drink(i),t);
}
for(int i=;i<=n;i++){
add(nu1(i),nu2(i));
}
} int vis[maxn],num[maxn]; bool bfs()
{
memset(vis,,sizeof(vis));
for(int i=;i<=*n++F+D+;i++){
num[i]=Head[i];
}
vis[s]=;
queue<int>q;
q.push(s);
int r=;
while(!q.empty()){
int u=q.front();
q.pop();
int k=Head[u];
while(k!=-){
if(!vis[v[k]]&&w[k]){
vis[v[k]]=vis[u]+;
q.push(v[k]);
}
k=Next[k];
}
}
return vis[t];
} int dfs(int u,int f)
{
if(u==t){return f;}
int &k=num[u];
int sum=;
while(k!=-){
if(vis[v[k]]==vis[u]+&&w[k]){
int d=dfs(v[k],min(f,w[k]));
f-=d;
w[k]-=d;
w[k^]+=d;
sum+=d;
}
k=Next[k];
}
return sum;
} int Dinic()
{
int ans=;
while(bfs()){
int f;
while((f=dfs(s,inf))>){
ans+=f;
}
}
return ans;
} int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
init();
scanf("%d%d%d",&n,&F,&D);
for(int i=;i<=n;i++){
int m1,m2;
scanf("%d%d",&m1,&m2);
int num;
for(int j=;j<=m1;j++){
scanf("%d",&num);
add(food(num),nu1(i));
}
for(int j=;j<=m2;j++){
scanf("%d",&num);
add(nu2(i),drink(num));
}
}
build();
printf("%d\n",Dinic());
return ;
}
Power Network POJ - 1459
题意：有发电厂用来发电，有用户用来用电，用中间商不赚差价，问电力的最大流量。
思路：好像也是一个板子题，就是输入有些许麻烦。
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-); int n,np,nc,m;
int s,t;
int Head[maxn],Next[maxn],v[maxn],w[maxn],cnt; void init()
{
s=n;t=n+;
memset(Head,-,sizeof(Head));
cnt=;
} void add(int x,int y,int z)
{
// cout<<x<<" "<<y<<" "<<z<<endl;
if(x==y){return;}
v[cnt]=y;
w[cnt]=z;
Next[cnt]=Head[x];
Head[x]=cnt++; v[cnt]=x;
w[cnt]=;
Next[cnt]=Head[y];
Head[y]=cnt++;
} char str[maxn];
int vis[maxn],num[maxn]; bool bfs()
{
memset(vis,,sizeof(vis));
for(int i=;i<=t;i++){
num[i]=Head[i];
}
vis[s]=;
queue<int>q;
q.push(s);
int r=;
while(!q.empty()){
int u=q.front();
q.pop();
int k=Head[u];
while(k!=-){
if(!vis[v[k]]&&w[k]){
vis[v[k]]=vis[u]+;
q.push(v[k]);
}
k=Next[k];
}
}
return vis[t];
} int dfs(int u,int f)
{
if(u==t){return f;}
int &k=num[u];
int sum=;
while(k!=-){
if(vis[v[k]]==vis[u]+&&w[k]){
int d=dfs(v[k],min(f,w[k]));
f-=d;
w[k]-=d;
w[k^]+=d;
sum+=d;
}
k=Next[k];
}
return sum;
} int Dinic()
{
int ans=;
while(bfs()){
int f;
while((f=dfs(s,inf))>){
ans+=f;
}
}
return ans;
} int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin); while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF){
init();
for(int i=;i<=m;i++){
scanf("%s",str);
int len =strlen(str);
int j,num = ;
int x,y,z;
for(j=;j<len;j++){
if(str[j]>=''&&str[j]<=''){num=num*+str[j]-'';}
else break;
}
x=num;num=;
for(j++;j<len;j++){
if(str[j]>=''&&str[j]<=''){num=num*+str[j]-'';}
else break;
}
y=num;num=;
for(j++;j<len;j++){
if(str[j]>=''&&str[j]<=''){num=num*+str[j]-'';}
else break;
}
z=num;
add(x,y,z);
} for(int i=;i<=np;i++){
scanf("%s",str);
int len = strlen(str);
int j=,x,y,num=;
for(j++;j<len;j++){
if(str[j]>=''&&str[j]<=''){num=num*+str[j]-'';}
else break;
}
x=num;num=;
for(j++;j<len;j++){
if(str[j]>=''&&str[j]<=''){num=num*+str[j]-'';}
else break;
}
y=num;num=;
add(s,x,y);
}
for(int i=;i<=nc;i++){
scanf("%s",str);
int len = strlen(str);
int j=,x,y,num=;
for(j++;j<len;j++){
if(str[j]>=''&&str[j]<=''){num=num*+str[j]-'';}
else break;
}
x=num;num=;
for(j++;j<len;j++){
if(str[j]>=''&&str[j]<=''){num=num*+str[j]-'';}
else break;
}
y=num;num=;
add(x,t,y);
}
printf("%d\n",Dinic());
} return ;
}
Escape HDU - 3605
题意：有很多人想跑路了，可是他们都有自己想去的星球，每个星球也有自己的容量，问所有人是否都可以去到自己的想去的星球上。
思路：这个人很多，把相同目的地的人合在一起才行。
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-); int Head[],Next[maxn],v[maxn],w[maxn],cnt;
int n,m,s,t;
int vis[],num[];
int sum[];
void init()
{
s=+m+;t=s+;
memset(sum,,sizeof(sum));
for(int i=;i<=t;i++){
Head[i]=-;
}
cnt=;
}
void add(int x,int y,int z)
{
// cout<<x<<" "<<y<<" "<<z<<endl;
if(x==y){return;}
v[cnt]=y;
w[cnt]=z;
Next[cnt]=Head[x];
Head[x]=cnt++; v[cnt]=x;
w[cnt]=;
Next[cnt]=Head[y];
Head[y]=cnt++;
} bool bfs()
{
memset(vis,,sizeof(vis));
for(int i=;i<=t;i++){
num[i]=Head[i];
}
vis[s]=;
queue<int>q;
q.push(s);
int r=;
while(!q.empty()){
int u=q.front();
q.pop();
int k=Head[u];
while(k!=-){
if(!vis[v[k]]&&w[k]){
vis[v[k]]=vis[u]+;
q.push(v[k]);
}
k=Next[k];
}
}
return vis[t];
} int dfs(int u,int f)
{
if(u==t){return f;}
int &k=num[u];
int sum=;
while(k!=-){
if(vis[v[k]]==vis[u]+&&w[k]){
int d=dfs(v[k],min(f,w[k]));
f-=d;
w[k]-=d;
w[k^]+=d;
sum+=d;
}
k=Next[k];
}
return sum;
} int Dinic()
{
int ans=;
while(bfs()){
int f;
while((f=dfs(s,inf))>){
ans+=f;
}
}
return ans;
} int plant(int x)
{
return x+;
} int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF){
init();
for(int i=;i<n;i++){
int num = ,x;
for(int j=;j<m;j++){
scanf("%d",&x);
num=num*+x;
}
sum[num]++;
}
for(int i=;i<;i++){
add(s,i,sum[i]);
}
for(int i=;i<;i++){
if(sum[i]){
int ss = i;
for(int j=m;j>=;j--){
if(ss&){add(i,plant(j),inf);}
ss>>=;
}
}
}
for(int i=;i<=m;i++){
int num = ;
scanf("%d",&num);
add(plant(i),t,num);
}
if(Dinic()==n){printf("YES\n");}
else printf("NO\n");
} return ;
}
ACM Computer Factory POJ - 3436
题意：造电脑了，每一个工厂有若干入厂状态和一个出厂状态，问整个系统的最大产量。
思路：枚举，如果有某家工厂的某个入厂状态和另一家工厂的出厂状态相同，那就连一条边。题目要求输出路径，整个在Dinic的DFS里面加记录一下就行了，这个题是有SPJ的，所以可以写的随心一点
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-);
int p,n;
int vis[],num[];
int Head[],Next[maxn],v[maxn],w[maxn],cnt;
vector<int>num1[];
int num2[];
int s,t,flows;
void init()
{
memset(Head,-,sizeof(Head));
s=*n+;t=s+;
}
void add(int x,int y,int z)
{
// cout<<x<<" "<<y<<" "<<z<<endl;
if(x==y){return;}
v[cnt]=y;
w[cnt]=z;
Next[cnt]=Head[x];
Head[x]=cnt++; v[cnt]=x;
w[cnt]=;
Next[cnt]=Head[y];
Head[y]=cnt++;
} bool bfs()
{ memset(vis,,sizeof(vis));
for(int i=;i<=t;i++){
num[i]=Head[i];
}
vis[s]=;
queue<int>q;
q.push(s);
int r=;
while(!q.empty()){
int u=q.front();
q.pop();
int k=Head[u];
while(k!=-){
if(!vis[v[k]]&&w[k]){
vis[v[k]]=vis[u]+;
q.push(v[k]);
}
k=Next[k];
}
}
return vis[t];
}
struct node
{
int u,v,w;
};
queue<node>q;
int anss;
int dfs(int u,int f)
{
if(u==t){return f;}
int &k=num[u];
int sum=;
while(k!=-){
if(vis[v[k]]==vis[u]+&&w[k]){
int d=dfs(v[k],min(f,w[k]));
if(d>){
if(u!=s&&v[k]!=t&&u>n){
q.push(node{u-n,v[k],d});
anss++;
}
w[k]-=d;
w[k^]+=d;
return d;
}
}
k=Next[k];
}
return sum;
}
int Dinic()
{
int ans=;
while(bfs()){
int f;
while((f=dfs(s,inf))>){
ans+=f;
}
}
return ans;
}
int a[];
int u;
void num_dfs(int t,int ans)
{
if(t==p+){
num1[u].push_back(ans);
return;
}
if(a[t]==){
num_dfs(t+,ans*);
}
else if(a[t]==){
num_dfs(t+,ans*+);
}
else{
num_dfs(t+,ans*);
num_dfs(t+,ans*+);
}
} int sta(int x)
{
return x;
} int endd(int x)
{
return x+n;
} int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin); scanf("%d%d",&p,&n);
init();
for(int i=;i<=n;i++){
num1[i].clear();num2[i]=;
}
for(int i=;i<=n;i++){
scanf("%d",&flows);
add(sta(i),endd(i),flows);
u=i;
for(int j=;j<=p;j++){
scanf("%d",&a[j]);
}
num_dfs(,);
for(int j=;j<=p;j++){
int h;
scanf("%d",&h);
num2[i]=num2[i]*+h;
}
}
for(int i=;i<=n;i++){
int siz = num1[i].size();
if(num2[i]==(<<p)-){
add(endd(i),t,inf);
}
for(int j=;j<siz;j++){
if(num1[i][j]==){add(s,sta(i),inf);}
for(int k=;k<=n;k++){
if(num1[i][j]==num2[k]){
add(endd(k),sta(i),inf);
}
}
}
}
printf("%d ",Dinic());
printf("%d\n",anss);
while(!q.empty()){
printf("%d %d %d\n",q.front().u,q.front().v,q.front().w);
q.pop();
}
return ;
}
Minimum Cost POJ - 2516
题意：有供货源给商店老板供货，每一种商品都有各自的对于每一个供应商都有其存储量，对于每一个商店都有其需求量，对于每一对商店和供应商的组合，运输都有其花费，求最大流量时的最大花费。
思路：每一种商品分别建图，不然会TLE，因为边太多了。
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
//const ll Inf = 999999999999999999;
//const int mod = 1000000007;
//const double eps = 1e-6;
//const double pi = acos(-1); int n,m,k,ans;
int Head[*],Next[maxn],v[maxn],cap[maxn],w[maxn],cnt;
bool vis[*];
int dis[*];
int prevv[*];
int preve[*];
int s,t,all;
void init()
{
s=;t=*k*(n+m)+;
memset(Head,-,sizeof(Head));
ans=cnt=;
} int sshop(int x,int s)
{
return *k*(x-)+s;
} int eshop(int x,int y)
{
return sshop(x,y)+k;
} int ssup(int x,int y)
{
return n*k*+y+(x-)*k*;
} int esup(int x,int y)
{
return ssup(x,y)+k;
} void add(int x,int y,int z,int f){
// cout<<x<<" "<<y<<" "<<z<<" "<<f<<endl;
v[cnt]=y;
w[cnt]=z;
cap[cnt]=f;
Next[cnt]=Head[x];
Head[x]=cnt++; v[cnt]=x;
w[cnt]=-z;
cap[cnt]=;
Next[cnt]=Head[y];
Head[y]=cnt++;
} bool spfa(){
queue<int>q;
memset(vis,,sizeof(vis));
for(int i=;i<=t;i++){
dis[i]=inf;
} dis[s]=;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int k=Head[u];k!=-;k=Next[k]){
if(cap[k]&&dis[v[k]]>dis[u]+w[k]){
dis[v[k]]=dis[u]+w[k];
prevv[v[k]]=u;
preve[v[k]]=k; if(!vis[v[k]]){
vis[v[k]]=true;
q.push(v[k]);
}
}
}
}
if(dis[t]==inf){return false;}
else return true;
}int anss=;
int min_cost_flow(){
while(spfa()){
anss++;
for(int i=t;i!=s;i=prevv[i]){
int k=preve[i];
cap[k]-=;
cap[k^]+=;
}
ans+=dis[t];
}
return ans;
} int input1[][];
int input2[][]; void build(int kk)
{
init();
for(int i=;i<=n;i++){
add(sshop(i,kk),eshop(i,kk),,input1[i][kk]);
}
for(int i=;i<=m;i++){
add(ssup(i,kk),esup(i,kk),,input2[i][kk]);
}
for(int i=;i<=n;i++){
add(s,sshop(i,kk),,inf);
}
for(int i=;i<=m;i++){
add(esup(i,kk),t,,inf);
}
} int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
while(scanf("%d%d%d",&n,&m,&k)!=EOF&&(n||m||k)){
init();all=;anss=;
for(int i=;i<=n;i++){
for(int j=;j<=k;j++){
int input;
scanf("%d",&input);
all+=input;
input1[i][j]=input;
}
} for(int i=;i<=m;i++){
for(int j=;j<=k;j++){
int input;
scanf("%d",&input);
input2[i][j]=input;
}
}
int ans=;
for(int i=;i<=k;i++){
build(i);
for(int j=;j<=n;j++){
for(int s=;s<=m;s++){
int input;
scanf("%d",&input);
add(eshop(j,i),ssup(s,i),input,inf);
}
}
ans+=min_cost_flow();
}
if(anss!=all)ans=-;
printf("%d\n",ans);
} return ;
}
Cyclic Tour HDU- 1853
题意：某个人要转圈圈，每个点之走一次，问最小花费。
思路：把每个点拆开（pi1和pi2），有边的话就建一条pi2到pj1的边，源点到每个p1建边容量为一，花费为0，汇点同理，然后网络流即可。建图虽然没有体现环，但是如果网络流跑满了，就说明每个点都在环内了（每个点的出度和入度都是1）
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-);
int m,n,s,t,ans,anss;
int Head[],Next[maxn],v[maxn],w[maxn],cap[maxn],cnt;
bool vis[];
int dis[],prevv[],preve[];
void init()
{
anss=;
memset(Head,-,sizeof(Head));
s=,t=*n+;ans=cnt=;
}
void add(int x,int y,int z,int f){
// cout<<x<<C" "<<y<<" "<<z<<" "<<f<<endl;
v[cnt]=y;
w[cnt]=z;
cap[cnt]=f;
Next[cnt]=Head[x];
Head[x]=cnt++; v[cnt]=x;
w[cnt]=-z;
cap[cnt]=;
Next[cnt]=Head[y];
Head[y]=cnt++;
} bool spfa(){
queue<int>q;
memset(vis,,sizeof(vis));
for(int i=;i<=t;i++){
dis[i]=inf;
} dis[s]=;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int k=Head[u];k!=-;k=Next[k]){
if(cap[k]&&dis[v[k]]>dis[u]+w[k]){
dis[v[k]]=dis[u]+w[k];
prevv[v[k]]=u;
preve[v[k]]=k; if(!vis[v[k]]){
vis[v[k]]=true;
q.push(v[k]);
}
}
}
}
// fuck(dis[t])
if(dis[t]==inf){return false;}
else return true;
}
int min_cost_flow(){
while(spfa()){
anss++;
for(int i=t;i!=s;i=prevv[i]){
int k=preve[i];
cap[k]-=;
cap[k^]+=;
}
ans+=dis[t];
}
// fuck(ans)
return ans;
} int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF){
init();
for(int i=;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y+n,z,);
} for(int i=;i<=n;i++){
add(i+n,t,,);
add(s,i,,);
}
int ans = min_cost_flow();
if(anss!=n){ans=-;}
printf("%d\n",ans);
} return ;
}
Fox And Dinner CodeForces - 510E
题意：n个数字，组成若干个环，相邻的两个数相加必须是质数，输出组合方式。
思路：和上一题相同，就是跑满之后才能看出来满足题意。具体方法是，分为奇数和偶数，源点到奇数的权值为2，偶数到汇点的权值是2，如果相加为质数，奇数到偶数权值为1.跑满的话，说明每个数旁边都有两个数，满足题意。然后通过深搜找出途中的环。因为满足题意，每个点只有两个相邻的点，所以可以无脑向下搜。注意网络流途中的边权变化，导致技术和偶数的有效边权值是不一样的。
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-);
int n,s,t;
int nums[];
int vis[maxn],num[maxn];
int prime[maxn],cur;
bool check[maxn];
int Head[],Next[maxn],v[maxn],w[maxn],cnt; void init()
{
memset(Head,-,sizeof(Head));
cnt=;
s=,t=n+;
} void primes()
{
for(int i=;i<;i++){
if(!check[i]){
prime[cur++]=i;
}
for(int j=;j<cur;j++){
if(i*prime[j]>){
break;
}
check[i*prime[j]]=i;
if(i%prime[j]==){
break;
}
}
}
} void add(int x,int y,int z)
{
// if(x!=s&&y!=t)cout<<x<<" "<<y<<" "<<z<<endl;
if(x==y){return;}
v[cnt]=y;
w[cnt]=z;
Next[cnt]=Head[x];
Head[x]=cnt++; v[cnt]=x;
w[cnt]=;
Next[cnt]=Head[y];
Head[y]=cnt++;
} bool bfs()
{
memset(vis,,sizeof(vis));
for(int i=;i<=t;i++){
num[i]=Head[i];
}
vis[s]=;
queue<int>q;
q.push(s);
int r=;
while(!q.empty()){
int u=q.front();
q.pop();
int k=Head[u];
while(k!=-){
if(!vis[v[k]]&&w[k]){
vis[v[k]]=vis[u]+;
q.push(v[k]);
}
k=Next[k];
}
}
return vis[t];
} int dfs(int u,int f)
{
if(u==t){return f;}
int &k=num[u];
int sum=;
while(k!=-){
if(vis[v[k]]==vis[u]+&&w[k]){
int d=dfs(v[k],min(f,w[k]));
if(d>){
w[k]-=d;
w[k^]+=d;
return d;
}
}
k=Next[k];
}
return sum;
}
int Dinic()
{
int ans=;
while(bfs()){
int f;
while((f=dfs(s,inf))>){
ans+=f;
}
}
return ans;
}
stack<int>st;
void dfs(int t)
{
vis[t]=;
st.push(t);
for(int k=Head[t];k!=-;k=Next[k]){
if(v[k]==||v[k]==n+){continue;}
if(vis[v[k]]){continue;}
if(nums[t]%==&&w[k]){dfs(v[k]);}
if(nums[t]%==&&!w[k]){dfs(v[k]);}
}
vis[t]=-;
} queue<int>q[];
int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin); primes();
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&nums[i]);
}init();
for(int i=;i<=n;i++){
if(nums[i]&){add(s,i,);}
else{add(i,t,);}
for(int j=i+;j<=n;j++){
if(!check[nums[i]+nums[j]]){
if(nums[i]&){add(i,j,);}
else{add(j,i,);}
}
}
}
if(Dinic()!=n){printf("Impossible\n");return ;} int numi = ;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++){
if(!vis[i]){
dfs(i);numi++;
while(!st.empty()){
q[i].push(st.top());
st.pop();
}
}
}
printf("%d\n",numi);
for(int i=;i<=n;i++){
if(!q[i].empty()){
printf("%d",q[i].size());
while(!q[i].empty()){
printf(" %d",q[i].front());
q[i].pop();
}
printf("\n");
} }
return ;
}
以上8题全靠建图+贴板子，建好了图就完成了90%。
这就是暑训的8题了。接下来还是暑训网络流的题，一共四题，不过被收录到图论专题中。
Ombrophobic Bovines POJ - 2391
题意：有奶牛要去避难，有n个避难所，第i个避难所已经有了ai头牛，可以容纳bi头牛，从第i个避难所到第j个避难所需要花费ti时间，所有奶牛同时出发，问最小花费的时间。
思路：我一开始想到的是使用最小费用最大流，把原来的ans+=dis[t]改成ans=max(ans,dis[t])即可，建图方式就是拆点（设为拆成x,y吧），源点到xi容量为ai.费用为0，yi到汇点容量为bi，费用为0，如果i与j之间有边，就建边xi到yj，容量正无穷，花费为所需时间。但是这样做是错误的，原因在于，最小费用最大流执行过程中，会优先选择最短的路，也就是说，如果可以留在本地，那么牛一定会留下来，但这样不是最优解，避难所如果是：
1 0
1 1
1 1
0 1
如果所有路径距离都是1，那么其实每头牛向下走一格才是最优解，而不是23的留在原地，1走到4.
所以这题的正解其实是最短路+二分+最大流。
至于为什么要拆点，我记得白书上说，如果要限制点的流量，那么便可以拆点，可是这里并没有限制流量，那么为什么要拆点捏，实际上是因为，在二分建图的过程中，小于mid的边就被连上了，拆点了的话，可以保证从i到j的过程没有经过其他的点，这样的mid限制才有意义。这里的没有经过其他的点，仅仅是指，在二分建图过程中，实际上从逻辑上分析，牛肯定是要经过其他的点的。
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
//const int mod = 1000000007;
//const double eps = 1e-6;
//const double pi = acos(-1);
ll mp[][];
int Head[],Next[maxn],v[maxn],cnt;
int vis[],num[];
int num1[],num2[maxn];
ll w[maxn];
int n,m,s,t;
ll all;
void init()
{
all= ;
memset(Head,-,sizeof(Head));
cnt=;s=,t=n*+;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
mp[i][j]=Inf;
}
}
} void add(int x,int y,int z)
{
// cout<<x<<" "<<y<<" "<<z<<endl;
if(x==y){return;}
v[cnt]=y;
w[cnt]=z;
Next[cnt]=Head[x];
Head[x]=cnt++; v[cnt]=x;
w[cnt]=;
Next[cnt]=Head[y];
Head[y]=cnt++;
} bool bfs()
{
memset(vis,,sizeof(vis));
for(int i=;i<=t;i++){
num[i]=Head[i];
}
vis[s]=;
queue<int>q;
q.push(s);
int r=;
while(!q.empty()){
int u=q.front();
q.pop();
int k=Head[u];
while(k!=-){
if(!vis[v[k]]&&w[k]){
vis[v[k]]=vis[u]+;
q.push(v[k]);
}
k=Next[k];
}
}
return vis[t];
} ll dfs(int u,ll f)
{
if(u==t){return f;}
int &k=num[u];
ll sum=;
while(k!=-){
if(vis[v[k]]==vis[u]+&&w[k]){
ll d=dfs(v[k],min(f,w[k]));
if(d>){
w[k]-=d;
w[k^]+=d;
return d;
}
}
k=Next[k];
}
return sum;
}
ll Dinic()
{
ll ans=;
while(bfs()){
ll f;
while((f=dfs(s,inf))>){
ans+=f;
}
}
return ans;
} void floyd()
{
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
}
}
}
} void build(ll x)
{
t=n+;
cnt=;memset(Head,-,sizeof(Head));
for(int i=;i<=n;i++){
add(s,i,num1[i]);
add(i,t,num2[i]);
// add(i,i+n,inf);
}
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
if(mp[i][j]<=x){
add(i,j,inf);
add(j,i,inf);
}
}
} } bool check(ll x)
{
build(x);
if(Dinic()==all){return true;}
return false;
} int main()
{
// ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin); scanf("%d%d",&n,&m);
init();
for(int i=;i<=n;i++){
scanf("%d%d",&num1[i],&num2[i]);
all+=num1[i];
} for(int i=;i<=m;i++){
int x,y;
ll z;
scanf("%d%d%lld",&x,&y,&z);
mp[x][y]=mp[y][x]=min(mp[y][x],z);
}
floyd();
ll l=,r=Inf,ans=-;
while(r>=l){
// fuck("______________")
ll mid=(r+l)/;
if(check(mid)){r=mid-;ans=mid;}
else l=mid+;
}
if(ans==Inf){ans=-;}
printf("%lld",ans); return ;
}
Budget POJ - 2396
题意：就是给一个矩阵要满足的条件，具体是每行之和，每列之和，以及每个数的大小限制，要求构建出一个矩阵。
思路：有上下界的网络流。
明天我再单独写一篇博客纪念这题～～～～
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-); int n,m,S,T,s,t;
int vis[maxn],num[maxn];
int Head[maxn],Next[maxn],v[maxn],w[maxn],cnt;
int mp[][];
int mph[][];
int mpl[][];
bool flag; void init()
{
S=;T=n+m+;s=T+;t=T+;
memset(Head,-,sizeof(Head));
memset(mpl,,sizeof(mpl));
for(int i=;i<;i++){
for(int j=;j<;j++){
mph[i][j]=inf;
mp[i][j]=;
}
}
cnt=;flag=false;
} void add(int x,int y,int z)
{
v[cnt]=y;
w[cnt]=z;
Next[cnt]=Head[x];
Head[x]=cnt++; v[cnt]=x;
w[cnt]=;
Next[cnt]=Head[y];
Head[y]=cnt++;
} bool bfs()
{
memset(vis,,sizeof(vis));
for(int i=;i<=t;i++){
num[i]=Head[i];
}
vis[s]=;
queue<int>q;
q.push(s);
int r=;
while(!q.empty()){
int u=q.front();
q.pop();
int k=Head[u];
while(k!=-){
if(!vis[v[k]]&&w[k]){
vis[v[k]]=vis[u]+;
q.push(v[k]);
}
k=Next[k];
}
}
return vis[t];
} int dfs(int u,int f)
{
if(u==t){return f;}
int &k=num[u];
int sum=;
while(k!=-){
if(vis[v[k]]==vis[u]+&&w[k]){
int d=dfs(v[k],min(f,w[k]));
if(d>){
w[k]-=d;
w[k^]+=d;
return d;
}
}
k=Next[k];
}
return sum;
}
int Dinic()
{
int ans=;
while(bfs()){
int f;
while((f=dfs(s,inf))>){
ans+=f;
}
}
return ans;
} int row(int x)
{
return x+;
} int col(int x)
{
return x+n+;
} int main()
{
int TT;
scanf("%d",&TT);
while(TT--){
int all=;
scanf("%d%d",&n,&m);
init();
int x;
for(int i=;i<=n;i++){
scanf("%d",&x);
add(S,t,x);add(s,row(i),x);all+=x;
}
for(int j=;j<=m;j++){
scanf("%d",&x);
add(s,T,x);
add(col(j),t,x);all+=x;
}
add(T,S,inf);
int q;
scanf("%d",&q);
while(q--){
int r,c,t;
char s[];
scanf("%d%d%s%d",&r,&c,s,&t); if(r!=&&c!=){
if(s[]=='='){
mpl[row(r)][col(c)]=max(mpl[row(r)][col(c)],t);
mph[row(r)][col(c)]=min(mph[row(r)][col(c)],t);
}
else if(s[]=='>'){
mpl[row(r)][col(c)]=max(mpl[row(r)][col(c)],t+);
}
else if(s[]=='<'){
mph[row(r)][col(c)]=min(mph[row(r)][col(c)],t-);
}
}
else if(r==&&c!=){
for(int i=;i<=n;i++){
if(s[]=='='){
mpl[row(i)][col(c)]=max(mpl[row(i)][col(c)],t);
mph[row(i)][col(c)]=min(mph[row(i)][col(c)],t);
}
else if(s[]=='>'){
mpl[row(i)][col(c)]=max(mpl[row(i)][col(c)],t+);
}
else if(s[]=='<'){
mph[row(i)][col(c)]=min(mph[row(i)][col(c)],t-);
}
}
}
else if(r!=&&c==){
for(int j=;j<=m;j++){
if(s[]=='='){
mpl[row(r)][col(j)]=max(mpl[row(r)][col(j)],t);
mph[row(r)][col(j)]=min(mph[row(r)][col(j)],t);
}
else if(s[]=='>'){
mpl[row(r)][col(j)]=max(mpl[row(r)][col(j)],t+);
}
else if(s[]=='<'){
mph[row(r)][col(j)]=min(mph[row(r)][col(j)],t-);
}
}
}
else{
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(s[]=='='){
mpl[row(i)][col(j)]=max(mpl[row(i)][col(j)],t);
mph[row(i)][col(j)]=min(mph[row(i)][col(j)],t);
}
else if(s[]=='>'){
mpl[row(i)][col(j)]=max(mpl[row(i)][col(j)],t+);
}
else if(s[]=='<'){
mph[row(i)][col(j)]=min(mph[row(i)][col(j)],t-);
}
}
}
}
}
for(int i=row();i<=row(n);i++){
for(int j=col();j<=col(m);j++){
if(mpl[i][j]>mph[i][j]){flag=true;break;}
add(i,j,mph[i][j]-mpl[i][j]);
add(s,j,mpl[i][j]);
add(i,t,mpl[i][j]);
all+=mpl[i][j];
}
}
if(flag){printf("IMPOSSIBLE\n\n");continue;} int ans=Dinic();
if(ans!=all){printf("IMPOSSIBLE\n\n");continue;}
for(int i=;i<=n+;i++){
for(int k=Head[i];k!=-;k=Next[k]){
if(v[k]>=col()&&v[k]<=col(m)){
mp[i-][v[k]-n-]+=w[k^]+mpl[i][v[k]];
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<m;j++){
printf("%d ",mp[i][j]);
}
printf("%d\n",mp[i][m]);
}
printf("\n");
}
return ;
}