USACO 5.4.5 TeleCowmunication 奶牛的電信 telecow
本文正體字版由OpenCC轉換
算法和4.4的pollutant control(求最小邊割集)類似,但這道題是求最小點割集。
我們可以把每個點i拆成兩個點i1,i2,這兩個點之間建立一條邊權爲1的有向弧。對於原圖中邊(i,j),建立(i2,j1)和(j2,i1)兩條邊權爲∞的有向弧。這樣就把求最小點割轉化成了求最小邊割。
根據最大流最小割定理:源S到匯T的網絡最大流等於S與T間最小邊割集的容量和。只需對新圖求網絡最大流,記爲netflow,在這裏我用了Dinic。這樣就完成了第一問,結果爲netflow。
對於第二問,要求出最小割集。對於每個點i(非c1,c2),把邊(i1,i2)去掉,求最大流,記爲nowflow,記當前找到的最小割集中元素的數量爲cnt。如果netflow-cnt=nowflow+1,那麼點i一定是最小割集中的割點,記錄下來。否則將邊(i1,i2)重新加上。直到cnt=netflow,當前找的集合就是最小割集。
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3644 KB]
Test 2: TEST OK [0.011 secs, 3640 KB]
Test 3: TEST OK [0.011 secs, 3644 KB]
Test 4: TEST OK [0.000 secs, 3644 KB]
Test 5: TEST OK [0.000 secs, 3640 KB]
Test 6: TEST OK [0.011 secs, 3640 KB]
Test 7: TEST OK [0.000 secs, 3644 KB]
Test 8: TEST OK [0.011 secs, 3640 KB]
Test 9: TEST OK [0.032 secs, 3640 KB]
Test 10: TEST OK [0.054 secs, 3644 KB]
Test 11: TEST OK [0.097 secs, 3640 KB]
All tests OK.
Your program ('telecow') produced all correct answers! This is your
submission #5 for this problem. Congratulations!
第一次寫Dinic,很冗長。
/*
ID: cmykrgb1
PROG: telecow
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 201
#define INF 0x7FFFFFFF
using namespace std;
class Tadjl
{
public:
int cnt;
int to[MAX];
Tadjl(){cnt=0;}
void ins(int k){to[++cnt]=k;}
};
class Tqueue
{
private:
long first,last;
long list[MAX*MAX];
public:
long size;
Tqueue()
{
reset();
}
void reset()
{
first=1;
last=size=0;
}
void ins(long k)
{
size++;
list[++last]=k;
}
long del()
{
size--;
return list[first++];
}
};
class Tstack
{
public:
int stack[MAX];
int top;
int min,p;
void reset()
{
top=0;
min=INF;
}
Tstack()
{
reset();
}
void ins(int k)
{
stack[++top]=k;
}
void del()
{
top--;
}
};
ifstream fi("telecow.in");
ofstream fo("telecow.out");
Tqueue Q;
Tstack AP;
int c1,c2,RN,RM,S,T,netflow;
Tadjl adjl[MAX];
int odis[MAX][MAX],dis[MAX][MAX],Flow[MAX][MAX];
int level[MAX],set[MAX];
bool used[MAX];
void init()
{
int i,a,b,a1,a2,b1,b2,c;
fi >> RN >> RM >> c1 >> c2;
if (c1>c2) {c=c1;c1=c2;c2=c;}
for (i=1;i<=RN;i++)
{
a=i*2-1;b=i*2;
adjl[a].ins(b);
dis[a][b]=1;
adjl[b].ins(a);
dis[b][a]=0;
}
for (i=1;i<=RM;i++)
{
fi >> a >> b;
if (a>b) {c=a;a=b;b=c;}
a1=a*2-1;a2=a1+1;
b1=b*2-1;b2=b1+1;
adjl[a2].ins(b1);
dis[a2][b1]=INF;
adjl[b1].ins(a2);
dis[b1][a2]=0;
adjl[b2].ins(a1);
dis[b2][a1]=INF;
adjl[a1].ins(b2);
dis[a1][b2]=0;
}
S=c1*2;
adjl[T=c2*2-1].cnt=0;
memcpy(odis,dis,sizeof(dis));
}
void Dinic_level()
{
int i,j,k;
Q.reset();
memset(used,0,sizeof(used));
memset(level,0,sizeof(level));
Q.ins(S);
while (Q.size)
{
i=Q.del();
used[i]=true;
for (k=1;k<=adjl[i].cnt;k++)
{
j=adjl[i].to[k];
if (!dis[i][j]) continue;
if (used[j] || j==1) continue;
level[j]=level[i]+1;
Q.ins(j);
}
}
}
void Dinic_Argument()
{
int i,u,v;
AP.stack[0]=S;
for (i=1;i<=AP.top;i++)
{
u=AP.stack[i-1];
v=AP.stack[i];
if (dis[u][v]<AP.min)
{
AP.min=dis[u][v];
AP.p=u;
}
}
for (i=AP.top;i>=1;i--)
{
u=AP.stack[i-1];
v=AP.stack[i];
Flow[u][v]+=AP.min;
dis[u][v]-=AP.min;
dis[v][u]+=AP.min;
}
}
bool Dinic_dfs(int u)
{
int outdegree=0;
int i,v;
bool B;
if (u!=T)
{
for (i=1;i<=adjl[u].cnt;i++)
{
v=adjl[u].to[i];
if (level[v]==level[u]+1 && dis[u][v])
{
outdegree++;
AP.ins(v);
B=Dinic_dfs(v);
AP.del();
if (B && u!=AP.p)
return true;
}
}
if (outdegree==0)
level[u]=0;
}
else
{
Dinic_Argument();
return true;
}
return false;
}
void Dinic()
{
memset(Flow,0,sizeof(Flow));
for (;;)
{
Dinic_level();
if (level[T]==0)
return;
AP.reset();
Dinic_dfs(S);
}
}
int getflow()
{
int i,flow=0;
for (i=1;i<=RN*2;i++)
flow+=Flow[S][i];
return flow;
}
void Getset()
{
int i,a,b,nowflow,cnt=0;
Dinic();
netflow=getflow();
for (i=1;i<=RN;i++)
{
if (i!=c1 && i!=c2)
{
a=i*2-1;b=a+1;
odis[a][b]=0;
memcpy(dis,odis,sizeof(odis));
Dinic();
nowflow=getflow();
if (nowflow+1==netflow-cnt)
set[++cnt]=i;
else
odis[a][b]=1;
}
if (cnt==netflow)
return;
}
}
void print()
{
int i;
fo << netflow << endl << set[1];
for (i=2;i<=netflow;i++)
fo <<' ' << set[i];
fo << endl;
fi.close();
fo.close();
}
int main()
{
init();
Getset();
print();
return 0;
}
上次修改時間 2017-02-03