加载中…
个人资料
lovedream
lovedream
  • 博客等级:
  • 博客积分:0
  • 博客访问:60,165
  • 关注人气:40
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

SGU185——最短路+最大流

(2011-10-27 11:14:27)
标签:

杂谈

分类: 图论

求无向网珞中边集不相交的两条最短路。

直观的想法是两次费用流增广,但是一直WA on 20……想了很久想不通,只好按照网上给出的方法,先最短路预处理,取最短路上得边即dis[v]==dis[u]+w[u][v];构成网络后增广两次,然后DFS输出。

 

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;

int dis[410],w[410][410],cap[410][410],pre[410];
int c;
bool vis[410];

void maxflow(int s,int t,int n)
{
    int i,j,k,tt;
    memset(vis,0,sizeof(vis));
    dis[s]=0;

    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();

        for(i=1;i<=n;i++)if(cap[u][i]>0&&!vis[i])
        {
            vis[i]=1;q.push(i);
            pre[i]=u;
        }
    }
    if(!vis[t])
        return ;
    for(int u=t;u-s;u=pre[u])
        cap[pre[u]][u]--,cap[u][pre[u]]++;
}
int ans[410];
void dfs(int n,int N)
{
    if(n==N)
    {
        printf("%d\n",n);
        return;
    }

    for(int i=1;i<=N;i++)if(cap[n][i]==0&&w[n][i]+dis[n]==dis[i])
    {
        printf("%d ",n),dfs(i,N),cap[n][i]=1;
        return ;
    }
}
int main()
{
    int n,m,i,j,u,v,d,t,k,tt;

    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            w[i][j]=w[j][i]=100000000;
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&u,&v,&d),w[v][u]=w[u][v]=d;
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;

    for(i=1;i<=n;i++)
    {
        for(j=1,tt=100000000;j<=n;j++)if(!vis[j]&&dis[j]>=0&&dis[j]<tt)
            tt=dis[k=j];
        vis[k]=1;
        for(j=1;j<=n;j++)if(!vis[j]&&(dis[j]<0||dis[j]>dis[k]+w[k][j]))
            dis[j]=dis[k]+w[k][j],pre[j]=k;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)if(w[i][j]&&dis[j]==dis[i]+w[i][j])
            cap[i][j]=1;
    maxflow(1,n,n);
    if(!vis[n])
    {
        printf("No solution\n");
        return 0;
    }
    maxflow(1,n,n);
    if(!vis[n])
    {
        printf("No solution\n");
        return 0;
    }
    dfs(1,n);
    dfs(1,n);
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有