Home > Old Blog Posts > USACO 4.4.2 Pollutant Control

USACO 4.4.2 Pollutant Control


看了Nocow的翻译真有几分无奈……
描述

你第一天接手三鹿牛奶公司就发生了一件倒霉的事情:公司不小心发送了一批有三聚氰胺的牛奶。很不幸,你发现这件事的时候,有三聚氰胺的牛奶已经进入了送货网。这个送货网很大,而且关系复杂。你知道这批牛奶要发给哪个零售商,但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成,每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候,有必要保证它不被送到零售商手里,所以必须使某些运输卡车停止运输,但是停止每辆卡车都会有一定的经济损失。你的任务是,在保证坏牛奶不送到零售商的前提下,制定出停止卡车运输的方案,使损失最小。

{批注:先前不知是哪个写了一个要不得的翻译,这才是正常的翻译,读起来也觉得比较健康——Cow-Tsc} {修改下,更现实——pyh119}

格式

PROGRAM NAME: milk6

INPUT FORMAT:

(file milk6.in) 第一行: 两个整数N(2<=N<=32)、M(0<=M<=1000), N表示仓库的数目,M表示运输卡车的数量。仓库1代 表发货工厂,仓库N代表有三聚氰胺的牛奶要发往的零售商。 第2..M+1行: 每行3个整数Si,Ei,Ci。其中Si,Ei表示这 辆卡车的出发仓库,目的仓库。Ci(0 <= C i <= 2,000,000) 表示让这辆卡车停止运输的损失。
OUTPUT FORMAT:

(file milk6.out) 第1行两个整数c、t,c表示最小的损失,T表示要停止的最少卡车数。接下来t 行表示你要停止哪几条线路。如果有多种方案使损失最小,输出停止的线路最少的方案。如果仍然还有相同的方案,请选择开始输入顺序最小的。

SAMPLE INPUT

4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

SAMPLE OUTPUT

60 1
3

题解

很明显地,这是一个最小割的模型,设每边的权值为原始权值,则最大流的值就是最小割的容量,即最小损失。现在有两个问题:停止的线路数,使开始输入顺序最小
为解决这两个问题,可将每边的权值修改为500000+i+500000*1001*c,这个式子有什么用呢?首先,每边的权值都加上500000,那么最大流(maxflow%(500000*1001))/500000就是停止的线路的数量,取500000的原因是500000>(0+999)*1000/2,即最大情况下0~999的i的和,否则可能由于i的值而使结果偏大。i项的含义就很明显了,为使输入顺序最小。最后一项中的1001则是因为最多有1000条边,所以500000*1001*c > 500000*1000,这三项分别独立,从而得出结果。
第一次编最小割,题解可能啰嗦了一些…

/*
ID: dementr1
PROG: milk6
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“milk6.in”);
ofstream fout(“milk6.out”);
long long v[40][40],s[1001],e[1001],c[1001],f[40][40],leave[40][40],level[40];
int M,N;
bool vis[1001]={false};
void init()
{
int i,j;
fin>>M>>N;
for(i=0;i<N;i++)
{
fin>>s[i]>>e[i]>>c[i];
v[s[i]][e[i]]+=500000+i+(long long)500000*1001*c[i];
}
fin.close();
}
void createlevel()
{
int save[1001]={},closed=-1,open=0,now,i,j;
memset(level,0,sizeof(level));
memset(leave,0,sizeof(leave));
level[1]=0;
save[0]=1;
for(i=1;i<=M;i++)
for(j=1;j<=M;j++)
leave[i][j]=v[i][j]-f[i][j];
for(i=1;i<=M;i++)
for(j=1;j<=M;j++)
if(f[i][j]>0) leave[j][i]=f[i][j];
while(closed<open)
{
closed++;
now=save[closed];
for(i=2;i<=M;i++)
if(leave[now][i]>0)
if(level[i]==0)
{
open++;
save[open]=i;
level[i]=level[now]+1;
}
}
}
long long dinic()
{
long long p[1001]={},u,i,min,ans=0;
p[0]=1;
p[1]=1;
while(1)
{
createlevel();
if(level[M]==0) break;
while(1)
{
u=p[p[0]];
if(u!=M)
{
bool flag=false;
for(i=1;i<=M;i++)
if(level[i]==level[u]+1&&leave[u][i]>0)
{
p[0]++;
p[p[0]]=i;
flag=true;
break;
}
if(!flag)
{
p[0]–;
for(i=1;i<=M;i++)
if(level[i]==level[u]+1&&leave[u][i]>0)
level[i]=0;
level[u]=0;
}
}
if(u!=M&&p[0]<=0) break;
if(u==M)
{
min=leave[p[1]][p[2]];
for(i=2;i<p[0];i++)
if(leave[p[i]][p[i+1]]<min) min=leave[p[i]][p[i+1]];
for(i=1;i<p[0];i++)
f[p[i]][p[i+1]]+=min;
for(i=1;i<p[0];i++)
if(leave[p[i]][p[i+1]]-min==0)
{
p[0]=i;
break;
}
ans+=min;
break;
}
}
}
return ans;
}
void floodfill(int k)
{
int i;
vis[k]=true;
for(i=1;i<=M;i++)
if(!vis[i]&&(leave[k][i]>0)||f[i][k]>0)
floodfill(i);
}
void print(long long ans)
{
int i;
fout<<ans/(500000*1001)<<” “<<(ans%(500000*1001))/500000<<endl;
for(i=0;i<N;i++)
if(vis[s[i]]&&!vis[e[i]])
fout<<i+1<<endl;
}
int main()
{
long long ans;
init();
ans=dinic();
floodfill(1);
print(ans);
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: