P1344 [USACO4.4]追查坏牛奶Pollutant Control
题目描述
你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。
输入输出格式
输入格式：
第一行: 两个整数\(N(2<=N<=32)\)、\(M(0<=M<=1000)\), \(N\)表示仓库的数目，\(M\)表示运输卡车的数量。仓库1代 表发货工厂，仓库\(N\)代表有三聚氰胺的牛奶要发往的零售商。 第\(2..M+1\)行: 每行3个整数\(S_i,E_i,C_i\)。其中\(S_i,E_i\)表示这 辆卡车的出发仓库，目的仓库。\(C_i(0 <= C_i <= 2,000,000)\) 表示让这辆卡车停止运输的损失。
输出格式：
两个整数\(C\)、\(T\)：\(C\)表示最小的损失，\(T\)表示在损失最小的前提下，最少要停止的卡车数。
第一问很显然直接连上权值有向边直接最小割了。
第二问需要统计最小的割边数量。
我们先把第一问断开的边权置1，表示可以取，然后把其他的正向边置\(inf\)，表示不能取，反向边仍然置0。再次跑最小割。
这时候最小割割去最少的边使图分成了两半，置\(inf\)使不合法的边不会被割去。
Code:
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N=35;
const int M=1010;
const int inf=0x3f3f3f3f;
int head[N],Next[M<<1],to[M<<1],edge[M<<1],cnt=1;
void add(int u,int v,int w)
{
Next[++cnt]=head[u];to[cnt]=v;edge[cnt]=w;head[u]=cnt;
Next[++cnt]=head[v];to[cnt]=u;edge[cnt]=0;head[v]=cnt;
}
int dep[N],n,m;
bool bfs()
{
queue <int > q;
q.push(1);
memset(dep,0,sizeof(dep));
dep[1]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=Next[i])
{
int v=to[i];
if(!dep[v]&&edge[i])
{
dep[v]=dep[u]+1;
q.push(v);
if(v==n) return 1;
}
}
}
return 0;
}
int dfs(int now,int flow)
{
if(now==n) return flow;
int rest=flow,k;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(edge[i]&&dep[v]==dep[now]+1)
{
k=dfs(v,min(edge[i],rest));
if(!k) dep[v]=0;
rest-=k;
edge[i]-=k;
edge[i^1]+=k;
}
}
return flow-rest;
}
void init()
{
scanf("%d%d",&n,&m);
int u,v,w;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
}
int dinic()
{
int maxflow=0,flow;
while(bfs())
while(flow=dfs(1,inf)) maxflow+=flow;
return maxflow;
}
void work()
{
printf("%d ",dinic());
for(int i=2;i<=cnt;i+=2)
{
if(!edge[i])
edge[i]=1;
else
edge[i]=inf;
edge[i+1]=0;
}
printf("%d\n",dinic());
}
int main()
{
init();
work();
return 0;
}
2018.7.1