285484026

「网络流 24 题」航空路线问题
「网络流 24 题」航空路线问题题解:求两条最大权不相交路径,用map将城市string映射到城市编号i,然后将每...
扫描右侧二维码阅读全文
25
2018/10

「网络流 24 题」航空路线问题

「网络流 24 题」航空路线问题
题解:求两条最大权不相交路径,用map将城市string映射到城市编号i,然后将每个城市i拆成Xi和Yi并且连接一条容量为1,权值为0的边,然后从源点向第一个点连接容量为1,权值为0的边,输出好麻烦啊!

#include <bits/stdc++.h>

const int MAXN = 1000000,INF = 10000000;

using namespace std;

int n,v,s,t,e = 2;
int head[MAXN],pri[MAXN],dis[MAXN];
bool inq[MAXN],vis[MAXN],flag,last;
string s1,s2,str[100];

map<string,int>city;

struct node{
    int u,v,w,c,f,next;
}edge[MAXN];

inline void addedge(int u,int v,int w,int c){
    edge[e] = (node){u,v, w,c,0,head[u]};head[u] = e++;
    edge[e] = (node){v,u,-w,0,0,head[v]};head[v] = e++;
}

inline void init()
{
    scanf("%d %d",&n,&v);
    for(int i = 1;i <= n;i++) {
        cin>>str[i];
        city[str[i]] = i;
    }
    s = 0;t = 2 * n + 1;
    for(int i = 2;i < n;i++) addedge(i,i+n,0,1);
    addedge(s,1,0,2);addedge(2*n,t,0,2);
    addedge(1,1+n,0,2);addedge(n,2*n,0,2);
    
    for(int i = 1;i <= v;i++){
        cin>>s1>>s2;
        addedge(city[s1]+n,city[s2],-1,INF);
    }
}
queue<int>Q;
inline bool spfa(){
    for(int i = s;i <= t;i++){
        inq[i] = false;
        dis[i] = INF;
        pri[i] = 0;
    }
    Q.push(s);dis[s] = 0;inq[s] = true;
    while(!Q.empty()){
        int x = Q.front();Q.pop();inq[x] = false;
        for(int i = head[x];i;i = edge[i].next){
            node E = edge[i];
            if(dis[E.v] > dis[x] + E.w && E.c > E.f){
                dis[E.v] = dis[x] + E.w;
                pri[E.v] = i;
                if(!inq[E.v]){
                    Q.push(E.v);
                    inq[E.v] = true;
                }
            }
        }
    }
    return pri[t] ? true : false;
}

void dfs_1(int x)
{
    Q.push(x-n);
    if(x == 2*n){flag = true;return;}
    vis[x-n] = true;
    for(int i = head[x];i;i = edge[i].next){
        node E = edge[i];
        if(E.f == 1 && !vis[E.v]){
            dfs_1(E.v+n);
            if(flag == true) return;
        }
    }
    if(flag == true) return;
}

stack<int>sta;
void dfs_2(int x)
{
    sta.push(x-n);
    if(x == 2*n){flag = true;return;}
    vis[x-n] = true;
    for(int i = head[x];i;i = edge[i].next){
        node E = edge[i];
        if(E.f == 1 && !vis[E.v]){
            dfs_2(E.v+n);
            if(flag == true) return;
        }
    }
    if(flag == true) return;
}

inline void MCMF(){
    int flow = 0,cost = 0,tmp;
    while(spfa()){
        tmp = INF;
        for(int i = pri[t];i;i = pri[edge[i^1].v])
            tmp = min(tmp,edge[i].c-edge[i].f);
        for(int i = pri[t];i;i = pri[edge[i^1].v]){
            edge[i].f += tmp;
            edge[i^1].f -= tmp;
            cost += tmp * edge[i].w;
        }
        flow += tmp;
    }
    if(flow == 2) {
        printf("%d\n",-cost);
        flag = false;dfs_1(1+n);
        while(!Q.empty()){
            cout<<str[Q.front()]<<endl;
            if(Q.front() == n)last = true;
            Q.pop();
        }
        if(last == false)cout<<str[n]<<endl;
        flag = false;dfs_2(1+n);
        while(!sta.empty()){
            if(sta.top() != n)cout<<str[sta.top()]<<endl;
            sta.pop();
        }        
    }
    else printf("No Solution!\n");
}

int main()
{
    #ifdef hi_archer
      freopen("input.txt", "r", stdin);
    #endif
    init();
    MCMF();
    return 0; 
} 
Last modification:October 25th, 2018 at 03:57 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment