LG2770/LOJ6122 航空路线问题 费用流 网络流24题

问题描述

LG2770

LOG6122

题解

教训：关掉流同步之后就不要用其他输入输出方式了。

拆点。

两个拆点之间连\((1,1)\)，其他连\((1,0)\)

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

void read(int &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

const int maxn=203;
const int maxm=1000003;

const int INF=0x3f3f3f3f;
int flag;
int n,m;
map<string,int>mp;
string s[maxn],s1,s2; 

int Head[maxn],Next[maxm],to[maxm],w[maxm],co[maxm],tot=1;
int S,T,maxflow,ans;

void add(int x,int y,int flow,int cost){
    to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=flow,co[tot]=cost;
}

int dis[maxn],pre[maxm],now[maxn];
bool vis[maxn];

void dfs1(int x){
    cout<<s[x]<<endl;
    vis[x]=1;
    for(int i=Head[x];i;i=Next[i]){
        int y=to[i];
        if(y>n&&y<=2*n&&w[i]==0){
            dfs1(y-n);break;
        }
    }
}

void dfs2(int x){
    vis[x]=1;
    for(int i=Head[x];i;i=Next[i]){
        int y=to[i];
        if(y>n&&y<=2*n&&w[i]==0&&!vis[y-n]){
            dfs2(y-n);break;
        }
    }
    cout<<s[x]<<endl;
}

bool spfa(){
    memset(dis,0xcf,sizeof(dis)),memset(vis,0,sizeof(vis));memset(pre,0,sizeof(pre));
    now[S]=INF;queue<int>q;q.push(S);vis[S]=1;dis[S]=0;
    while(!q.empty()){
        int x=q.front();vis[x]=0;q.pop();
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i],len=w[i],cost=co[i];
            if(!len||dis[y]>=dis[x]+cost) continue;
            dis[y]=dis[x]+cost,now[y]=min(now[x],len);
            pre[y]=i;
            if(!vis[y]){q.push(y);vis[y]=1;} 
        }
    }
    return dis[T]!=(int)0xcfcfcfcf;
}

void upd(){
    maxflow+=now[T],ans+=dis[T]*now[T];
    int p=T;
    while(p!=S){
        int k=pre[p];
        w[k]-=now[T],w[k xor 1]+=now[T];
        p=to[k xor 1];
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];mp[s[i]]=i;
    }
    S=n*2+1,T=S+1;
    add(S,n+1,INF,0);add(n+1,S,0,0);
    add(n,T,INF,0);add(T,n,0,0);
    for(int i=1;i<=n;i++){
        if(i!=1&&i!=n) add(i+n,i,1,1),add(i,i+n,0,-1);
        else add(i+n,i,2,1),add(i,i+n,0,-1);
    }
    for(int i=1;i<=m;i++){
        cin>>s1;cin>>s2;
        int x=mp[s1],y=mp[s2];
        if(x>y) swap(x,y);
        if(x==1&&y==n) flag=1;
        add(x,y+n,1,0),add(y+n,x,0,0);
    }
    while(spfa()) upd();
    if(maxflow==2) cout<<ans-2<<endl;
    else if(maxflow==1&&flag){
        cout<<2<<endl;cout<<s[1]<<endl<<s[n]<<endl<<s[1]<<endl;return 0;
    }
    else{
        cout<<"No Solution!"<<endl;return 0;
    }
    memset(vis,0,sizeof(vis));
    dfs1(1);dfs2(1);
    return 0;
}