[SGU 213]求最大独立割、最短路

【题目大意】 给定一个无向图，图中有一个起点S和一个终点T。要求选K个集合S1，S2，…，SK，每个集合都含有图中的一些边，任意两个不同的集合的交集为空。并且从图中任意去掉一个集合，S到T都没有通路。要求K尽量大。

【算法分析】如果你会dinic的话，就很容易有感觉。。。
实际上就是弄一个层次图，设d[i]为从S到i点的最短路，然后每一个割集分别就是所有d[x]=dis和d[x]=dis+1相连的边的集合。

【其它】1A
994092 01.02.10 19:03 edward 213 .CPP Accepted 25 ms 23423 kb
【CODE】
#include #include #include #define N 500
struct gtp{int x,y,next;}g[2000000];
int n,e,S,T,ls[N],d[N],v[N],list[N];

void init(){
scanf("%d%d%d%d",&n,&e,&S,&T);
for (int i=1;i<=e;i++){
scanf("%d%d",&g[i].x,&g[i].y);
g[i+e].x=g[i].y;
g[i+e].y=g[i].x;
}
for (int i=1;i<=2*e;i++){
g[i].next=ls[g[i].x];
ls[g[i].x]=i;
}   
}   

void spfa(){
memset(d,60,sizeof(d));
memset(v,0,sizeof(v));
d[S]=0; v[S]=1; list[0]=S;
int head=-1,tail=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (int t=ls[list[head]];t;t=g[t].next)
if (d[g[t].x]+1d[g[t].y]=d[g[t].x]+1;
if (!v[g[t].y]){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}   
}
v[list[head]]=0;
}   
}

void print(){
printf("%dn",d[T]);
for (int dis=0;disint num=0;
for (int i=1;i<=n;i++)
if (d[i]==dis)
for (int t=ls[i];t;t=g[t].next)
if (d[g[t].y]==dis+1){
num++;
if (t>e) list[num]=t-e;
else list[num]=t;
}
printf("%d",num);
for (int i=1;i<=num;i++) printf(" %d",list[i]);
printf("n");
}   
}   

int main(){
init();
spfa();
print();
return 0;
}