USACO 5.4.5 TeleCowmunication 奶牛的电信 telecow
算法和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