[SGU185] 网络流、求无重复边的最短路**

【题目大意】给定一个无向图,让你求两条从1到N的最短路,使得它们没用重复的边。

【算法分析】先dijkstra,然后如果d[i]+a[i][j]==d[j]的话连边[i,j](流量为1),然后求最大流,如果流量<2的话,就是无解,否则从源点dfs到汇点两次(顺着有流量的边,经过的就标记),输出路径即可。 【其它】这题空间卡得很紧。。。搞了几次才过。 【CODE】
#include #include #include #define N 401
#define E 160001
struct gtp{int x,y,op,next,c;}g[E];
int n,m,e,a[N][N];
int ls[N],cur[N],fa[N],num[N],d[N],v[N];
int flow;

void init(){
memset(a,60,sizeof(a));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
if (wa[x][y]=w;
a[y][x]=w;
}   
}
m*=2;   
}   

void dijkstra(){
memset(v,0,sizeof(v));
for (int i=2;i<=n;i++) d[i]=a[1][i];
d[1]=0; v[1]=1;
for (;;){
int mm=a[0][0],j;
for (int i=1;i<=n;i++)
if (v[i]==0 && d[i]mm=d[i];
j=i;
}
if (mm==a[0][0]) break;
v[j]=1;
for (int i=1;i<=n;i++)
if (d[j]+a[j][i]}   
}   

inline void addedge(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].next=ls[x]; ls[x]=e;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}   

void build(){
e=0;
memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i!=j && d[i]+a[i][j]==d[j]) addedge(i,j,1);
}   

void relabel(int k){
int mm=n;
cur[k]=ls[k];
for (int t=ls[k];t!=0;t=g[t].next)
if (g[t].c>0 && d[g[t].y]d[k]=mm+1;
}   

void change(){
flow++;
for (int i=n;i!=1;i=g[fa[i]].x){
g[fa[i]].c–;
g[g[fa[i]].op].c++;
}   
}   

void sap(){
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for (int i=1;i<=n;i++) cur[i]=ls[i];
int i=1; num[0]=n;
while (d[1]for (;cur[i]!=0;cur[i]=g[cur[i]].next)
if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
if (cur[i]==0){
if (–num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=1) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==n){
change();
i=1;
}   
}   
}   
}   

bool dfs(int k){
if (k==n){
printf("%dn",n);
return true;
}
printf("%d ",k);
for (int t=ls[k];t!=0;t=g[t].next)
if ((t&1) && g[t].c==0){
g[t].c=-1;
if (dfs(g[t].y)) return true;
}
return false;
}   

int main(){
init();
dijkstra();
build();
sap();
if (flow<2) printf("No solutionn");
else{
dfs(1);
dfs(1);
}
return 0;
}   

留下评论

您的电子邮箱地址不会被公开。