学会了网络流，就经常闲的没事儿刷网络流……于是乎来一发题解。
1. COGS2093 花园的守护之神
题意：给定一个带权无向图，问至少删除多少条边才能使得s-t最短路的长度变长。
用Dijkstra或者SPFA跑出来s-t最短路，然后把最短路DAG上的每条边的容量设为1，跑最小割即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF ((~((1)<<(31)))>>(1))
using namespace std;
const int maxn=,maxe=;
struct edge1{int from,to,prev;long long dis;}e1[maxe<<];
struct edge2{int to,cap,prev;}e2[maxe<<];
struct node{
int x;
long long dis;
node(int x,long long dis):x(x),dis(dis){}
bool operator<(const node &a)const{return dis>a.dis;}
};
void addedge1(int,int,long long);
void addedge2(int,int,int);
void Dijkstra(int,long long*);
int Dinic();
void bfs();
int dfs(int,int);
int n,m,s,t,last1[maxn]={},len1=,last2[maxn],len2=,now[maxn],d[maxn],q[maxn],head,tail,x,y;
long long dis[maxn],redis[maxn],z;
bool vis[maxn];
int main(){
#define MINE
#ifdef MINE
freopen("greendam2002.in","r",stdin);
freopen("greendam2002.out","w",stdout);
#endif
memset(last2,-,sizeof(last2));
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=;i<=m;i++){
scanf("%d%d%lld",&x,&y,&z);
addedge1(x,y,z);
addedge1(y,x,z);
}
Dijkstra(s,dis);
Dijkstra(t,redis);
for(int i=;i<=(m<<);i++)if(dis[e1[i].from]+e1[i].dis+redis[e1[i].to]==dis[t]){
addedge2(e1[i].from,e1[i].to,);
addedge2(e1[i].to,e1[i].from,);
}
printf("%d",Dinic());
#ifndef MINE
printf("\n--------------------DONE--------------------\n");
for(;;);
#endif
return ;
}
void addedge1(int x,int y,long long z){
e1[++len1].from=x;
e1[len1].to=y;
e1[len1].dis=z;
e1[len1].prev=last1[x];
last1[x]=len1;
}
void addedge2(int x,int y,int z){
e2[len2].to=y;
e2[len2].cap=z;
e2[len2].prev=last2[x];
last2[x]=len2++;
}
void Dijkstra(int x,long long *dis){
memset(vis,,sizeof(vis));
priority_queue<node>q;
memset(dis,,sizeof(long long)*maxn);
dis[x]=;
q.push(node(x,));
while(!q.empty()){
x=q.top().x;
q.pop();
if(vis[x])continue;
vis[x]=true;
for(int i=last1[x];i;i=e1[i].prev)if(dis[e1[i].to]>dis[x]+e1[i].dis){
dis[e1[i].to]=dis[x]+e1[i].dis;
q.push(node(e1[i].to,dis[e1[i].to]));
}
}
}
int Dinic(){
int ans=;
for(;;){
bfs();
if(d[t]==INF)break;
memset(now,,sizeof(now));
ans+=dfs(s,INF);
}
return ans;
}
void bfs(){
int x;
fill_n(d+,n,INF);
d[s]=;
head=tail=;
q[tail++]=s;
while(head!=tail){
x=q[head++];
for(int i=last2[x];i!=-;i=e2[i].prev)if(e2[i].cap>&&d[e2[i].to]==INF){
d[e2[i].to]=d[x]+;
q[tail++]=e2[i].to;
}
}
}
int dfs(int x,int delta){
if(x==t||!delta)return delta;
int flow=,f;
for(int i=(now[x]?e2[now[x]].prev:last2[x]);i!=-;i=e2[i].prev)if(e2[i].cap>&&d[e2[i].to]==d[x]+){
now[x]=i;
f=dfs(e2[i].to,min(delta,e2[i].cap));
if(!f)continue;
e2[i].cap-=f;
e2[i^].cap+=f;
flow+=f;
delta-=f;
if(!delta)break;
}
return flow;
}
2. [NEERC 2003][POJ2125]有向图破坏
题意：给定一个有向图，可以删除一个点所有的出边，费用为wi；或者删除一个点所有的入边，费用为wi’，求把所有边都删掉所需的最少费用。
把点拆成出点和入点，有向边变成连接出点和入点的边，然后就是二分图最小权点覆盖问题。
其实这不是费用流，直接把s到出点和入点到t的边的容量设为对应的费用，其他边容量正无穷，再跑最大流就行。至于为什么，因为这是最小割，不是最小费用最大流。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF (0x3f3f3f3f)
using namespace std;
const int maxn=<<,maxe=;
struct edge{int to,cap,cost,prev;}e[maxe];
void addedge(int,int,int);
void insert(int,int,int);
int Dinic();
void bfs();
int dfs(int,int);
int n,m,s,t,last[maxn],len=,d[maxn],now[maxn],q[maxn],head,tail,tmp,x,y;
int main(){
#define MINE
#ifdef MINE
freopen("destroyingthegraph.in","r",stdin);
freopen("destroyingthegraph.out","w",stdout);
#endif
memset(last,-,sizeof(last));
scanf("%d%d",&n,&m);
s=(n<<)+;
t=s+;
for(int i=;i<=n;i++){
scanf("%d",&tmp);
addedge(i+n,t,tmp);
}
for(int i=;i<=n;i++){
scanf("%d",&tmp);
addedge(s,i,tmp);
}
while(m--){
scanf("%d%d",&x,&y);
addedge(x,y+n,INF);
}
printf("%d",Dinic());
#ifndef MINE
printf("\n-------------------------DONE-------------------------\n");
for(;;);
#endif
return ;
}
void addedge(int x,int y,int z){
insert(x,y,z);
insert(y,x,);
}
void insert(int x,int y,int z){
e[len].to=y;
e[len].cap=z;
e[len].prev=last[x];
last[x]=len++;
}
int Dinic(){
int ans=;
for(;;){
bfs();
if(d[t]==INF)break;
memset(now,,sizeof(now));
ans+=dfs(s,INF);
}
return ans;
}
void bfs(){
int x;
memset(d,,sizeof(d));
d[s]=;
head=tail=;
q[tail++]=s;
while(head!=tail){
x=q[head++];
for(int i=last[x];i!=-;i=e[i].prev)if(e[i].cap>&&d[e[i].to]>d[x]+){
d[e[i].to]=d[x]+;
q[tail++]=e[i].to;
}
}
}
int dfs(int x,int delta){
if(x==t||!delta)return delta;
int flow=,f;
for(int i=(now[x]?e[now[x]].prev:last[x]);i!=-;i=e[i].prev)if(e[i].cap>&&d[e[i].to]==d[x]+){
now[x]=i;
f=dfs(e[i].to,min(delta,e[i].cap));
if(!f)continue;
e[i].cap-=f;
e[i^].cap+=f;
flow+=f;
delta-=f;
if(!delta)break;
}
return flow;
}
3. [SGU252]铁路网
题意略，总之就是带边权的最小路径覆盖问题。
拆二分图，连带费用的边，然后一发最小费用最大流就行。必须最大流的原因在于这是最少路径条数覆盖，所以必须增广到最大流才能保证所求出的是最小路径覆盖。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=,maxe=;
struct edge{int to,cap,cost,prev;}e[maxe<<];
void addedge(int,int,int,int);
void insert(int,int,int,int);
void mincostmaxflow();
void SPFA();
int n,m,last[maxn],len=,dis[maxn],p[maxn],s,t,flow=,cost=,x,y,z;
bool inq[maxn];
int main(){
#define MINE
#ifdef MINE
freopen("railwaycommunication.in","r",stdin);
freopen("railwaycommunication.out","w",stdout);
#endif
memset(last,-,sizeof(last));
scanf("%d%d",&n,&m);
s=(n<<|);
t=s+;
for(int i=;i<=n;i++){
addedge(s,i,,);
addedge(i+n,t,,);
}
while(m--){
scanf("%d%d%d",&x,&y,&z);
addedge(x,y+n,,z);
}
mincostmaxflow();
printf("%d %d",n-flow,cost);
#ifndef MINE
printf("\n-------------------------DONE-------------------------\n");
for(;;);
#endif
return ;
}
void addedge(int x,int y,int z,int w){
insert(x,y,z,w);
insert(y,x,,-w);
}
void insert(int x,int y,int z,int w){
e[len].to=y;
e[len].cap=z;
e[len].cost=w;
e[len].prev=last[x];
last[x]=len++;
}
void mincostmaxflow(){
int delta,x;
for(;;){
SPFA();
if(dis[t]==0x3f3f3f3f)break;
delta=~(<<);
for(x=t;x!=s;x=e[p[x]^].to)delta=min(delta,e[p[x]].cap);
for(x=t;x!=s;x=e[p[x]^].to){
e[p[x]].cap-=delta;
e[p[x]^].cap+=delta;
cost+=e[p[x]].cost*delta;
}
flow+=delta;
}
}
void SPFA(){
int x;
memset(dis,,sizeof(dis));
memset(inq,,sizeof(inq));
queue<int>q;
q.push(s);
dis[s]=;
while(!q.empty()){
x=q.front();
q.pop();
inq[x]=false;
for(int i=last[x];i!=-;i=e[i].prev)if(e[i].cap>&&dis[e[i].to]>dis[x]+e[i].cost){
dis[e[i].to]=dis[x]+e[i].cost;
p[e[i].to]=i;
if(!inq[e[i].to]){
inq[e[i].to]=true;
q.push(e[i].to);
}
}
}
}
4. [ZJOI2010]网络扩容
题意：给定一张有向图，每条边都有一个容量C和一个将容量扩大1所需的费用W。求在不扩容的情况下，1到N的最大流和将1到N的最大流增加K所需的最小扩容费用。
每条边拆成两条边，一条容量为C费用为0，一条容量正无穷费用为W，然后跑费用为0时的最大流，再在残量网络上跑固定流量最小费用流即可。
一开始的最大流可以用Dinic之类的算法写，(懒得再写一份最大流的)也可以用费用流代替，只要在费用增大到大于0之前记录流量即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
const int maxn=,maxe=;
struct edge{int to,cap,cost,prev;}e[maxn<<];
void addedge(int,int,int,int);
void insert(int,int,int,int);
int Dinic();
void bfs();
int dfs(int,int);
int mincostflow();
void SPFA();
int n,m,k,last[maxn],len=,s,t,dis[maxn],now[maxn],q[maxn],head,tail,p[maxn],x,y,z,w;
bool inq[maxn];
int main(){
#define MINE
#ifdef MINE
freopen("networkzj2010.in","r",stdin);
freopen("networkzj2010.out","w",stdout);
#endif
memset(last,-,sizeof(last));
scanf("%d%d%d",&n,&m,&k);
s=;
t=n;
while(m--){
scanf("%d%d%d%d",&x,&y,&z,&w);
addedge(x,y,z,);
addedge(x,y,0x3f3f3f3f,w);
}
printf("%d ",Dinic());
printf("%d",mincostflow());
#ifndef MINE
printf("\n-------------------------DONE-------------------------\n");
for(;;);
#endif
return ;
}
void addedge(int x,int y,int z,int w){
insert(x,y,z,w);
insert(y,x,,-w);
}
void insert(int x,int y,int z,int w){
e[len].to=y;
e[len].cap=z;
e[len].cost=w;
e[len].prev=last[x];
last[x]=len++;
}
int Dinic(){
int ans=;
for(;;){
bfs();
if(dis[t]==0x3f3f3f3f)break;
memset(now,,sizeof(now));
ans+=dfs(s,~(<<));
}
return ans;
}
void bfs(){
int x;
memset(dis,,sizeof(dis));
dis[s]=;
head=tail=;
q[tail++]=s;
while(head!=tail){
x=q[head++];
for(int i=last[x];i!=-;i=e[i].prev)if(!e[i].cost&&e[i].cap>&&dis[e[i].to]>dis[x]+){
dis[e[i].to]=dis[x]+;
q[tail++]=e[i].to;
}
}
}
int dfs(int x,int delta){
if(x==t||!delta)return delta;
int flow=,f;
for(int i=(now[x]?e[now[x]].prev:last[x]);i!=-;i=e[i].prev)if(!e[i].cost&&e[i].cap>&&dis[e[i].to]==dis[x]+){
now[x]=i;
f=dfs(e[i].to,min(delta,e[i].cap));
if(!f)continue;
e[i].cap-=f;
e[i^].cap+=f;
flow+=f;
delta-=f;
if(!delta)break;
}
return flow;
}
int mincostflow(){
int ans=,x,delta;
for(;;){
SPFA();
if(dis[t]==0x3f3f3f3f)break;
delta=k;
for(x=t;x!=s;x=e[p[x]^].to)delta=min(delta,e[p[x]].cap);
for(x=t;x!=s;x=e[p[x]^].to){
e[p[x]].cap-=delta;
e[p[x]^].cap+=delta;
ans+=e[p[x]].cost*delta;
}
k-=delta;
if(!k)break;
}
return ans;
}
void SPFA(){
int x;
memset(dis,,sizeof(dis));
memset(inq,,sizeof(inq));
deque<int>q;
q.push_back(s);
dis[s]=;
while(!q.empty()){
x=q.front();
q.pop_front();
inq[x]=false;
for(int i=last[x];i!=-;i=e[i].prev)if(e[i].cap>&&dis[e[i].to]>dis[x]+e[i].cost){
dis[e[i].to]=dis[x]+e[i].cost;
p[e[i].to]=i;
if(!inq[e[i].to]){
inq[e[i].to]=true;
if(!q.empty()&&dis[e[i].to]<dis[q.front()])q.push_front(e[i].to);
else q.push_back(e[i].to);
}
}
}
}
5. 最小最大生成树
题意：给定一个带权无向连通图，求使得加入的权值为w的边(u,v)既能出现在最小生成树上也能出现在最大生成树上所需要删除的最少边数。
一条权为w的边(u,v)不能出现在最小生成树上的充要条件是u,v可以只借助边权<w的边而连通，所以直接把边权<w的所有边扔进图里，容量为1，然后跑u-v最小割即可。最大生成树同理。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF (0x3f3f3f3f)
using namespace std;
const int maxn=,maxe=;
struct edge1{int from,to,w;}ee[maxe];
struct edge{int to,cap,prev;}e[maxe<<];
void addedge(int,int,int);
int Dinic();
void bfs();
int dfs(int,int);
int n,m,last[maxn],len=,d[maxn],now[maxn],q[maxn],head,tail,s,t,w,ans=;
int main(){
#define MINE
#ifdef MINE
freopen("mstmn.in","r",stdin);
freopen("mstmn.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)scanf("%d%d%d",&ee[i].from,&ee[i].to,&ee[i].w);
scanf("%d%d%d",&s,&t,&w);
memset(last,-,sizeof(last));
for(int i=;i<=m;i++)if(ee[i].w<w){
addedge(ee[i].from,ee[i].to,);
addedge(ee[i].to,ee[i].from,);
}
ans+=Dinic();
memset(last,-,sizeof(last));
len=;
for(int i=;i<=m;i++)if(ee[i].w>w){
addedge(ee[i].from,ee[i].to,);
addedge(ee[i].to,ee[i].from,);
}
ans+=Dinic();
printf("%d",ans);
#ifndef MINE
printf("\n-------------------------DONE-------------------------\n");
for(;;);
#endif
return ;
}
void addedge(int x,int y,int z){
e[len].to=y;
e[len].cap=z;
e[len].prev=last[x];
last[x]=len++;
}
int Dinic(){
int ans=;
for(;;){
bfs();
if(d[t]==INF)break;
memset(now,,sizeof(now));
ans+=dfs(s,INF);
}
return ans;
}
void bfs(){
int x;
memset(d,,sizeof(d));
head=tail=;
q[tail++]=s;
d[s]=;
while(head!=tail){
x=q[head++];
for(int i=last[x];i!=-;i=e[i].prev)if(e[i].cap>&&d[e[i].to]>d[x]+){
d[e[i].to]=d[x]+;
q[tail++]=e[i].to;
}
}
}
int dfs(int x,int delta){
if(x==t||!delta)return delta;
int flow=,f;
for(int i=(now[x]?e[now[x]].prev:last[x]);i!=-;i=e[i].prev)if(e[i].cap>&&d[e[i].to]==d[x]+){
now[x]=i;
f=dfs(e[i].to,min(delta,e[i].cap));
if(!f)continue;
e[i].cap-=f;
e[i^].cap+=f;
flow+=f;
delta-=f;
if(!delta)break;
}
return flow;
}
6. [网络流24题]餐巾
题意略。
把每天拆成早上和晚上两个点，再新增一个源点s(可以理解为卖餐巾的地方……)，从s到每个早上连一条费用为买餐巾费用，容量正无穷的边，从每天早上到晚上连一条流量下界为所需餐巾数的边，从每天晚上向往后a天的早上连费用为快洗费用，流量正无穷的边，慢洗同理。再从每天晚上到后一天晚上连一条费用为0容量正无穷的边，表示餐巾没用上留到明天晚上。这样建图之后可以把每个流量理解为一条餐巾(到处流的餐巾……)，那么要求的就是满足那些下界的最小费用可行流。
带下界这个问题也很好说，把它的费用改成负无穷，容量为它的下界，那么跑最小费用流增广的时候一定会增广完它之后才会停止，所以这样转换之后可以保证所有下限都能够被满足。最后把费用减去这一堆负无穷即可。
其实三分贪心比起费用流来说又好写又快……
这份代码是我费用流没学好的时候写的，用的是dfs增广……Too young too simple……
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define LL long long
#define INF ((~(1<<31))>>1)
using namespace std;
const int maxn=<<;
struct edge{int to,cap,prev;LL cost;}e[];
void addedge(int,int,int,LL);
void insert(int,int,int,LL);
void mincostflow();
void SPFA();
int dfs(int,int);
int last[maxn],len=,now[maxn];
bool inq[maxn];
int n,a,b,s,t;
LL ca,cb,cc,c[maxn],dis[maxn],ans=0ll;
int main(){
freopen("napkin.in","r",stdin);
freopen("napkin.out","w",stdout);
memset(last,-,sizeof(last));
scanf("%d",&n);
a++;b++;
s=(n<<|);t=s+;
for(int i=;i<=n;i++)scanf("%lld",&c[i]);
scanf("%lld%d%lld%d%lld",&cc,&a,&ca,&b,&cb);
for(int i=;i<=n;i++){
ans+=c[i]*INF;
addedge(s,i,INF,cc);
addedge(i,i+n,c[i],-INF);
if(i<n)addedge(i+n,i+n+,INF,);
if(i+a<=n)addedge(i+n,i+a,INF,ca);
if(i+b<=n)addedge(i+n,i+b,INF,cb);
}
t=n+n;
mincostflow();
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return ;
}
void addedge(int x,int y,int z,LL w){
//printf("addedge(%d,%d,%d,%lld)\n",x,y,z,w);
insert(x,y,z,w);
insert(y,x,,-w);
}
void insert(int x,int y,int z,LL w){
e[len].to=y;
e[len].cap=z;
e[len].cost=w;
e[len].prev=last[x];
last[x]=len++;
}
void mincostflow(){
for(;;){
SPFA();
if(dis[t]>=0ll)break;
memset(now,,sizeof(now));
dfs(s,INF);
}
}
void SPFA(){
int x;
memset(inq,,sizeof(inq));
memset(dis,,sizeof(dis));
queue<int>q;
q.push(s);
dis[s]=;
while(!q.empty()){
x=q.front();
q.pop();
inq[x]=false;
for(int i=last[x];i!=-;i=e[i].prev)if(e[i].cap>&&dis[e[i].to]>dis[x]+e[i].cost){
dis[e[i].to]=dis[x]+e[i].cost;
if(!inq[e[i].to]){
inq[e[i].to]=true;
q.push(e[i].to);
}
}
}
}
int dfs(int x,int delta){
if(x==t||!delta)return delta;
int f;
for(int i=(now[x]?e[now[x]].prev:last[x]);i!=-;i=e[i].prev)if(e[i].cap>&&dis[e[i].to]==dis[x]+e[i].cost){
now[x]=i;
f=dfs(e[i].to,min(delta,e[i].cap));
if(!f)continue;
e[i].cap-=f;
e[i^].cap+=f;
ans+=e[i].cost*(LL)f;
return f;
}
return ;
}
7. COGS1632 搬运工
题意略，带权二分图点覆盖。
为了保证次数最小，把边权统一加上100000，然后跑最大流即可。最后的最小次数是流量/100000，最少费用是流量%100000。
不得不说这个建图比较机智……其实也是用大的屏蔽小的来实现优先级之类的玩意儿。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
struct edge{int to,prev,cap;}e[maxn*maxn<<];
void addedge(int,int,int);
void AddEdge(int,int,int);
int Dinic();
void bfs(int);
int dfs(int,int);
int last[maxn],d[maxn],now[maxn],q[maxn];
int n,len=,head,tail,s,t,tmp;
char c;
inline int MAIN(){
#define MINE
#ifdef MINE
freopen("worker.in","r",stdin);
freopen("worker.out","w",stdout);
#endif
memset(last,-,sizeof(last));
scanf("%d",&n);
for(int i=;i<=n;i++)for(int j=;j<=n;j++){
scanf(" %c",&c);
if(c=='*')addedge(i,j+n,(~(<<))>>);
}
s=n<<|;t=s+;
for(int i=;i<=n;i++){
scanf("%d",&tmp);
addedge(s,i,tmp+);
}
for(int i=;i<=n;i++){
scanf("%d",&tmp);
addedge(i+n,t,tmp+);
}
n=(n<<)+;
tmp=Dinic();
printf("%d %d",tmp/,tmp%);
#ifndef MINE
printf("\n-------------------------DONE-------------------------\n");
for(;;);
#endif
return ;
}
int hzoier=MAIN();
int main(){;}
void addedge(int x,int y,int z){
AddEdge(x,y,z);
AddEdge(y,x,);
}
void AddEdge(int x,int y,int z){
e[len].to=y;
e[len].cap=z;
e[len].prev=last[x];
last[x]=len++;
}
int Dinic(){
int ans=;
for(;;){
bfs(s);
if(d[t]>n)break;
memset(now,,sizeof(now));
ans+=dfs(s,~(<<));
}
return ans;
}
void bfs(int x){
memset(d,,sizeof(d));
d[x]=;
head=tail=;
q[tail++]=x;
while(head!=tail){
x=q[head++];
for(int i=last[x];i!=-;i=e[i].prev)if(e[i].cap>&&d[e[i].to]>n){
d[e[i].to]=d[x]+;
q[tail++]=e[i].to;
}
}
}
int dfs(int x,int delta){
if(x==t||!delta)return delta;
int flow=,f;
for(int i=now[x]?e[now[x]].prev:last[x];i!=-;i=e[i].prev)if(e[i].cap>&&d[e[i].to]==d[x]+){
now[x]=i;
f=dfs(e[i].to,min(delta,e[i].cap));
if(!f)continue;
e[i].cap-=f;
e[i^].cap+=f;
flow+=f;
delta-=f;
if(!delta)break;
}
return flow;
}