洛谷(航空路线问题)

链接：https://www.luogu.org/problemnew/show/P2770
思路：跟题解做的有点不一样，因为是要求经过城市的数量最大，所以跑最大费用最大流，拆点，然后点之间的边流量为1表示只能经过一次，cost为-1统计费用用来表示经过的点的数量，然后建立一个源点连向1，容量为2，费用为0，表示两条路，建立一个汇点连接n，容量为2，费用为0，当最大流为2的时候有解输出费用即为经过的城市，注意有以下需要注意的地方。
1、如果最大流为1（无解）但起点和终点有一条连边，则可以直接到达，需要特判。
2、两个城市建边的时候要从序号小的指向大的（即从西到东）（发现之前有些网络流的题都没在意过这个问题），这样才能保证能流到汇点里面去。
代码：

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

const int maxn = 1010;
const int INF = 1e9;
int n,m;
map<string,int> mat;
string name[maxn];
vector<int> path;
int vis[maxn];

struct edge{
    int from,to,cap,flow,cost;
};

struct MCMF{
    int n,m,s,t;
    vector<edge> edges;
    vector<int> G[maxn];
    int inq[maxn];
    int d[maxn];
    int p[maxn];
    int a[maxn];
    int flow;

    void init(int n){
        this->n = n;
        for(int i=0;i<=n;i++)G[i].clear();
        edges.clear();
    }

    void addedge(int from,int to,int cap,int cost){
        edges.push_back(edge{from,to,cap,0,cost});
        edges.push_back(edge{to,from,0,0,-cost});
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool spfa(int s,int t,int &flow,int &cost){
        for(int i=0;i<=n;i++)d[i] = INF;
        memset(inq,0,sizeof(inq));
        d[s] = 0;
        inq[s] = 1;
        p[s] =  0;
        a[s] = INF;
        queue<int> q;
        q.push(s);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for(int i = 0;i<G[u].size();i++){
                edge &e = edges[G[u][i]];
               // printf("%d %d %d",d[e.from],e.cost,d[e.to]);
                if(e.cap>e.flow&&d[e.to]>d[u] + e.cost){
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u],e.cap-e.flow);
                    if(!inq[e.to]){
                        q.push(e.to);
                        inq[e.to] = 1;
                    }
                    }
                }
            }
            if(d[t]==INF)return false;
            flow+=a[t];
            cost+=d[t]*a[t];
            int u = t;
            while(u!=s){
                edges[p[u]].flow+=a[t];
                edges[p[u]^1].flow-=a[t];
                u = edges[p[u]].from;
            }
            return true;
    } 

    int mincost(int s,int t){
        int flow = 0,cost = 0;
        while(spfa(s,t,flow,cost));
        this->flow = flow;
        return cost;
    }

    void print(int x){
        int now = x;
        if(x>n/2)now-=n/2;
        path.push_back(now);
        vis[now] = 1;
        for(int i=0;i<G[now].size();i++){
            edge e = edges[G[now][i]];
            if(e.to==n||e.to==0)continue;
            if(e.to>n/2)e.to-=n/2;
            if(e.flow&&!vis[e.to])print(e.to);
        }
    }
}solver;


int main(){
    cin>>n>>m;
    solver.init(2*n+1);
    int check = 0;
    for(int i=1;i<=n;i++){
        string a;
        cin>>a;
        mat[a] = i;
        name[i] = a;
        if(i!=1&&i!=n)
        solver.addedge(i+n,i,1,-1);
        else if(i==n)solver.addedge(2*n,n,2,-1);
        else if(i==1)solver.addedge(n+1,1,2,-1);
    }
    for(int i=0;i<m;i++){
        string a,b;
        cin>>a>>b;
        if((mat[a]==1&&mat[b]==n)||(mat[a]==n&&mat[b]==1))check = 1;
        if(mat[a]>mat[b])solver.addedge(mat[b],mat[a]+n,1,0);
        else
        solver.addedge(mat[a],mat[b]+n,1,0);
    }
    solver.addedge(0,1,2,0);
    solver.addedge(n,2*n+1,2,0);
    int res = solver.mincost(0,2*n+1);
    if(!solver.flow||(solver.flow==1&&!check))cout<<"No Solution!"<<endl;
    else if(solver.flow==1&&check==1)cout<<"2\n"<<name[1]<<endl<<name[n]<<endl<<name[1]<<endl;
    else{
        cout<<-res<<endl;
        solver.print(1);
        int len = 0;
        for(int i=0;i<path.size();i++){
            if(path[i]!=2*n+1&&path[i]!=0&&path[i]!=n)cout<<name[path[i]]<<endl;
            else if(path[i]==n){
                cout<<name[n]<<endl;
                len = i;
                break;
            }
        }
        for(int i=path.size()-1;i>len;i--){
            cout<<name[path[i]]<<endl;
        }
        cout<<name[1]<<endl;
    }
    return 0;
}