Archive

Archive for June, 2009

USACO 5.4.5 Telecowmunication

June 28, 2009 Leave a comment

描述

农夫约翰的奶牛们喜欢通过电邮保持联系,于是她们建立了一个奶牛电脑网络,以便互相交流。这些机器用如下的方式发送电邮:如果存在一个由c台电脑组成的序列a1,a2,…,a(c),且a1与a2相连,a2与a3相连,等等,那么电脑a1和a(c)就可以互发电邮。

很不幸,有时候奶牛会不小心踩到电脑上,农夫约翰的车也可能碾过电脑,这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了,于是与这台电脑相关的连接也就不可用了。

有两头奶牛就想:如果我们两个不能互发电邮,至少需要坏掉多少台电脑呢?请编写一个程序为她们计算这个最小值和与之对应的坏掉的电脑集合。

以如下网络为例:

              1*
             /
            3 - 2*

这张图画的是有2条连接的3台电脑。我们想要在电脑1和2之间传送信息。电脑1与3、2与3直接连通。如果电脑3坏了,电脑1与2便不能互发信息了。

描述

程序名: telecow

输入格式 第一行四个由空格分隔的整数:N,M,c1,c2.N是电脑总数(1<=N<=100),电脑由1到N编号。M是电脑之间连接的总数(1& lt;= M<=600)。最后的两个整数c1和c2是上述两头奶牛使用的电脑编号。连接没有重复且均为双向的(即如果c1与c2相连,那么c2与c1也相 连)。两台电脑之间至多有一条连接。电脑c1和c2不会直接相连。 第2到M+1行 接下来的M行中,每行包含两台直接相连的电脑的编号。

输出格式

输出共有两行。第一行是使电脑c1和c2不能互相通信需要坏掉的电脑数目的最小值。第二行是排好序的坏掉的电脑的编号列表。注意c1和c2都不能坏掉。如果有多种可能情况,输出第一个数最小的一种,如果第一个数相同,则输出第二个数最小的一种,依此类推。

样例输入(文件telecow.in)

3 2 1 2
1 3
2 3

样例输出(文件telecow.out)

1
3

仍旧是一道求最小割的题目,只不过这道题是求最小点割集,为此,我们需要把点转化为边,将每个点i拆为i1,i2,连一条有向边(i1,i2),权值为1,对于每一条边(i, j),转换为两条有向边(i2, j1)和(j2, i1),源点为1-1,汇点为N-2,对新图求最大流,流的容量即为最小割的容量。再用一次flood求出最小边割集,最后将边还原为点。

因为要求字典序最小,有向边(i1,i2)的权值可修改为6000+i (想一想为什么,参照USACO 4.4.2的题解),最后maxflow的值再除以6000即可。

/*
ID: dementr1
PROG: telecow
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“telecow.in”);
ofstream fout(“telecow.out”);
int v[300][300],f[300][300],leave[300][300],level[300],N,M,c1,c2;
bool vis[300]={false};
int inf=2000000000;
void init()
{
int from,to,i;
fin>>N>>M>>c1>>c2;
for(i=0;i<M;i++)
{
fin>>from>>to;
v[from*2][to*2-1]=inf;
v[to*2][from*2-1]=inf;
}
fin.close();
for(i=1;i<=N;i++)
{
if(i==c1||i==c2) v[i*2-1][i*2]=inf;
else
v[i*2-1][i*2]=i+6000;
}
}
void createlevel()
{
int save[300]={},closed=-1,open=0,now,i,j;
memset(level,0,sizeof(level));
memset(leave,0,sizeof(leave));
level[c1*2-1]=0;
save[0]=c1*2-1;
for(i=1;i<=N*2;i++)
for(j=1;j<=N*2;j++)
leave[i][j]=v[i][j]-f[i][j];
for(i=1;i<=N*2;i++)
for(j=1;j<=N*2;j++)
if(f[i][j]>0) leave[j][i]=f[i][j];
while(closed<open)
{
closed++;
now=save[closed];
for(i=1;i<=N*2;i++)
{
if(i==c1*2-1) continue;
if(leave[now][i]>0)
if(level[i]==0)
{
open++;
save[open]=i;
level[i]=level[now]+1;
}
}
}
}
int dinic()
{
int p[300]={},u,i,min,ans=0;
p[0]=1;
p[1]=c1*2-1;
while(1)
{
createlevel();
if(level[c2*2]==0) break;
while(1)
{
u=p[p[0]];
if(u!=c2*2)
{
bool flag=false;
for(i=1;i<=N*2;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<=N*2;i++)
if(level[i]==level[u]+1&&leave[u][i]>0)
level[i]=0;
level[u]=0;
}
}
if(u!=c2*2&&p[0]<=0) break;
if(u==c2*2)
{
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<=N*2;i++)
if(!vis[i]&&((leave[k][i]>0)||f[i][k]>0))
floodfill(i);

}
int main()
{
int i,ansi[300]={};
init();
int ans=dinic();
floodfill(c1*2-1);
fout<<ans/6000<<endl;
for(i=1;i<=N;i++)
if(vis[i*2-1]&&!vis[i*2])
ansi[++ansi[0]]=i;
for(i=1;i<ansi[0];i++) fout<<ansi[i]<<” “;
fout<<ansi[ansi[0]]<<endl;
return 0;
}

Advertisements
Categories: Old Blog Posts

USACO 4.4.2 Pollutant Control

June 28, 2009 Leave a comment

看了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

基于分层思想的网络流算法-dinic

June 27, 2009 Leave a comment

Categories: Old Blog Posts

usaco题目分类

June 27, 2009 Leave a comment

1:动态规划:

1.       背包问题:

2.2.2 Subset Sums 2.3.4 Money System 3.1.2 Score Inflation 3.1.6 Stamps

3.4.4 Raucous Rockers 4.1.1 Beef McNuggets 5.3.1 Milk Measuring

2. 最长不XX子序列:

4.3.1 Buy Low Buy Lower

3. 其他

1.5.2 Number Triangles 3.3.2 Shopping Offers 3.3.5 A Game 3.3.4 Home on the Range

5.3.4 Big Barn 5.4.2 Canada Tour 3.1.5 Contact

4. Tree-DP

2.3.2 Cow Pedigrees

2. 递推:

2.3.1 Longest Prefix 5.4.3 Character Recognition

3.图结构:

1.最短路径:

2.4.2 Overfencing 2.4.3 Cow Tours 2.4.4 Bessie Come Home 3.2.6 Sweet Butter

2. 最小环:

4.1.3 Fence Loops

3.欧拉回路:

3.1.1 Riding the Fence

4.最大流,最小割:

4.2.1 Drainage Ditches  4.2.2 Pollutant Control 5.4.5 TeleCowmunication

5. 二分图匹配

4.2.2 Perfect Stall

6.最小点基

5.3.3 NetWork Of Schools

7.拓扑排序

4.4.3 Frame Up

8。图的遍历

4.3.3 Street Race

9.最小生成树

3.1.1 Agri-Net

4. 枚举:

1.3.3 Calf Flac 1.2.4 Palindromic Squares 1.2.5 Dual Palindromes 1.4.2 The Clocks 1.4.3 Arithmetic Progressions 2.2.1 Preface Numbering 3.3.3 Camelot 3.2.4 Feed Ratios 2.2.3 Runaround Numbers 3.2.3 Spinning Wheels

5. 模拟:

1.1.1 Your Ride Is Here 1.1.2 Greedy Gift Givers 1.1.3 Friday the Thirteenth 1.1.4 Broken Necklace 1.2.2 Transformations 1.2.3 Name That Number 2.2.1 Preface Numbering 2.4.1 The Tamworth Two

6.搜索:

1.DFS:

1.5.4 Checker Challenge 1.4.1 Packing Rectangles 1.4.4 Mother’s Milk  1.5.3 Superprime Rib 2.1.4 Healthy Holsteins  2.1.5 Hamming Codes 2.2.3 Zero Sum 4.1.2 Fence Rails (DFS-ID)4.1.4 Cryptcowgraphy 4.2.4 Cowcycles 4.3.2 The Primes 4.3.4 Letter Game 5.2.3 Wisconsin Squares  5.2.1 Snail Trails  5.4.1 All Latin Squares 5.4.4 Betsy’s Tour

2.BFS:

2.1.1 The Castle 3.2.5 Magic Squares

7.贪心:

1.2.1 Milking Cows 1.3.1 Mixing Milk 1.3.2 Barn Repair 4.2.3 Job Processing

8.离散化:

3.1.4 Shaping Regions 5.3.2 Window Area  5.3.2 Window Area(线段树)

9.计算几何:

3.4.1 Closed Fences  5.1.1 Fencing the Cows

10.解析几何:

3.4.3 Electric Fence 5.2.2 Electric Fences

Categories: Old Blog Posts

finish USACO 4.2.1

June 25, 2009 Leave a comment

别被吓到,我是跳着做的……
第一次编网络流,dinic算法,学习了N多牛人的资料,在此感谢******……
纪念一下自己的辛勤劳动吧,10小时的奋战……

   Test 1: TEST OK [0.011 secs, 3476 KB]
   Test 2: TEST OK [0.011 secs, 3472 KB]
   Test 3: TEST OK [0.011 secs, 3476 KB]
   Test 4: TEST OK [0.000 secs, 3472 KB]
   Test 5: TEST OK [0.000 secs, 3476 KB]
   Test 6: TEST OK [0.000 secs, 3472 KB]
   Test 7: TEST OK [0.000 secs, 3476 KB]
   Test 8: TEST OK [0.000 secs, 3476 KB]
   Test 9: TEST OK [0.011 secs, 3472 KB]
   Test 10: TEST OK [0.000 secs, 3472 KB]
   Test 11: TEST OK [0.011 secs, 3476 KB]
   Test 12: TEST OK [0.000 secs, 3476 KB]
Categories: Old Blog Posts

June 24, 2009 Leave a comment

他突然凭空出现在那里。

两边的人群流动着,对他视而不见。他环视四周,人们——不,这些不知是什么东西的怪物,眼球离开了眼皮的遮罩,布满血丝,由一根视神经支撑着,不住地摇晃。他赶紧躲开,然而那触目惊心的一幕却仍旧在眼前回荡,挥之不去。

怪物!一群怪物!他的四肢颤颤发抖,想逃,又似被灌了铅一般,怎么也抽不动。那群眼球肆无忌惮地在空中捕捉着目标,有时似乎与他的目光接触,一个鄙夷的眼神便立即随之而来,令他只觉寒意四袭。一个人令你无法分辩冷眼与否,这实在是一件痛苦的事情。

他实在是一个标准的人。但在这群怪物的眼中,他倒成了所谓的怪物。

他的头尚能转动,他竭力避开这可憎的景象,把目光投向别处,那里是一支送葬的队伍。队伍中的人身穿丧服,朝向前方的一面为黑色,而背向前方的一面却是红色,他们都长着两面脸,正对着前方的一面正哭丧着,眼角抽搐,恨不得把身上所有的水都挤兑成泪珠,撒落在地上;背向的一面却暗自窃喜,嘴里不住念叨着的,似乎是在计算可从中得利的遗产数额。前面的人一边走着,一边撒着纸钱,后面的人又把纸钱捡起,递给前面的人。站在最后的人怒气冲冲地盯着自己前面的人那张窃笑的脸,倒像他自己就没有一样。

他突然感到身体被几滴冰凉的水刺痛。下雨了。然而雨滴是那样的肥硕,每一滴都有着一副狰狞的面孔,在空中扭曲着,它们丝毫没有掉下来的意思,反而吸引着草丛中仅剩的露珠,随它一同向天上升去。天似乎也开始阴暗了呢,他顺着雨珠向上望去,看到的却不是乌云,而是一台巨大的机器浮在空中,榨取着这世间仅剩的清凉,随后,又从另一个出口,吐出一堆堆的瓶子,上面依稀刻着“Coco Cola”的字样。他只感到一阵眩晕,定神再看,眩晕的却不是自己,而是草地上那仅存的绿色,正同露水一同渐渐升向空中,留下一片枯萎的痕迹。

他终于感到有些湿湿的东西打到了自己的肩膀——没错,终于是从上面掉下来的了。他扭头看去,却是一片血色,还散发着阵阵的腥臭味。而路边的行人,一边欢快地跑着,一边欢呼,仿佛在享受着雨露的甘霖。

背后传来划玻璃一般的刺耳的声音。

那是一群人,正在欣赏音乐会。

他终于要疯了。

正在这一瞬间,他的四肢又恢复了知觉。他竭力使自己挣脱那刺耳的声音,全身如同痉挛一般颤动。四周的人群停止了流动,几千对纠缠不清的眼球找到了一个共同的目标,将他围在半径不到1米的包围圈内。

“他在干什么?”其中一个眼球像是问。

“看上去像是在跳舞吧。”另一个眼球回答道。

“这也能算跳舞?”几千对眼球“刷”的一下蜕成了惨白。

他已紧紧地闭上了眼睛。他也试图闭上他的耳朵,他的嘴,甚至他的鼻子。他把自己封锁在自己的世界里。他的身体仍不住地痉挛着,只是这种痉挛已逐渐转为有意识的了,倒像是富有节奏感的律动。

血雨还在下吗?他不知道。他闭上了他的每一个毛孔,每一根汗毛,他将自己的皮肤锁入了石膏。

他跳着,跳着……旧的一批围观者早已厌烦离去,却又有新的一批替之而来。

七天后,在他倒下的地方,已踩出了一个不小的水坑。

Categories: Old Blog Posts

思想者-2

June 24, 2009 Leave a comment

大自然对每个人都是公平的。目盲者,双耳往往敏锐;耳聋者,视力往往非凡;即便是万般不幸,集盲聋哑于一身,如海伦·凯勒,她也获赠了一颗纯洁而高贵的心。有所得必有所失,有所失亦有所得,这便是大自然的公平之道。

由此,我突然萌生出一个奇异的想法。大自然对人的塑造,与游戏中属性点的分配有着异曲同工之妙。总的属性点都是一样的,关键就在于哪项分配的多,哪项分配的少。决不可能每一项都达到满值,也即所谓的人无完人;相反地,也决不可能每一项都是0,这便是个有所长吧。但无论如何分,总不会有人傻到把每一项都平均分配,这样看似缺陷都实现了最小化,然而同时也将优势削减到了最弱。在游戏中,攻击力强的很可能防御力弱,反之亦然,但这样才能体现出队伍中人与人的配合;所谓的平均者,则往往是孤独的。

我们不妨找些属性点研究研究。对于理性和感性,不妨设总属性点为100吧。对于常人,往往是50对50,或在40和60之间来回波动。这样的人实际上是最快乐的,既有理性之光指引自己前进的方向,又有感性之花在道路上洒满一片芬芳。再来看一看科学家的属性,令你吃惊的是,除了80理性20感性这种意料之内的组合外,20理性80感性也光荣地上了榜。这或许应了一句话:许多伟大的点子,往往是疯狂的。感性可以助人突破思维惯性的束缚,再加以理性的检验,有时也能产生智慧的火花。这样的火花虽少,但每一簇都能遍布天空。那么,100的纯理性和纯感性又是什么?对于前者,我能找到一个近似的实例——政治家。至少,在扮演这个角色时,需要的是100%的理性,一着不慎,满盘皆输,政治家每一个微小的举动都要经过深思熟虑的掂算。其中如汉武帝之类,王立群教授曾评论:“他是一个极其理智的人,他的理智近乎于冷酷。”这实在是对优秀的政治家无奈而真实的刻画。而对于后者,很抱歉,我还没有找到。或许某些精神病院的疯子,能被冠上失去理智的头衔。常人总还是要有些理性的,或多或少,就算是陈日光之流,理性也起码要分配1点吧。无论如何,他还并没有进精神病院,不是吗?

由此而言,所谓的强者,并非三头六臂,样样精通,他们也必定有薄弱之处;且薄弱之处愈薄弱,则强大之处愈强大。因此,每一个人都不必为自己的薄弱而痛苦,因为每一处薄弱都在铺垫你的强大。对精神病院的疯子来说,放心好了,至少他们不会关心自己的强弱,也自然看不到我的文章。

那么,就先唠到这儿吧。

Categories: Old Blog Posts