洛谷P2770 航空路线问题 最小费用流

水题.

本质上题目要求的是一个包含 $1$，$n$ 的最大环，所以每个点只可以经过一次.

那么就拆点，然后限制每个点的经过次数就行了.

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<vector>

#include<cstring>

#include<queue>

#include<string>

#include<map>

using namespace std;

const int maxn=800;

const int INF=1000000+23666;

typedef long long ll;

map<string,int>idx;

string A[maxn];

int viss[maxn];

int s,t,n;

struct Edge{

	int from,to,cap,cost;

	Edge(int u,int v,int c,int f):from(u),to(v),cap(c),cost(f){}

};

vector<Edge>edges;

vector<int>G[maxn];

struct MCMF{

    int d[maxn],inq[maxn],a[maxn],flow2[maxn];

    queue<int>Q;

    ll ans=0;

    int flow=0;

    void addedge(int u,int v,int c,int f){

    	edges.push_back(Edge(u,v,c,f));    //正向弧

    	edges.push_back(Edge(v,u,0,-f));   //反向弧

    	int m=edges.size();

    	G[u].push_back(m-2);

    	G[v].push_back(m-1);

    }

    int SPFA(){

    	for(int i=0;i<=n;++i)d[i]=INF,flow2[i]=INF;

    	memset(inq,0,sizeof(inq));int f=INF;

    	d[s]=0,inq[s]=1;Q.push(s);

        while(!Q.empty()){

        	int u=Q.front();Q.pop();inq[u]=0;

        	int sz=G[u].size();

        	for(int i=0;i<sz;++i){

                  Edge e=edges[G[u][i]];

                  if(e.cap>0&&d[e.to]>d[u]+e.cost){

                      a[e.to]=G[u][i];

                      d[e.to]=d[u]+e.cost;

                      flow2[e.to]=min(flow2[u],e.cap);

                      if(!inq[e.to]){inq[e.to]=1;Q.push(e.to);}

                  }

        	}

        }

        if(d[t]==INF)return 0;

        f=flow2[t];

        flow+=f;

        int u=edges[a[t]].from;

        edges[a[t]].cap-=f;

        edges[a[t]^1].cap+=f;

        while(u!=s){

        	edges[a[u]].cap-=f;

        	edges[a[u]^1].cap+=f;

        	u=edges[a[u]].from;

        }

        ans+=(ll)(d[t]*f);

        return 1;

    }

    int maxflow(){

        while(SPFA());

        return flow;

    }

    ll getcost(){return ans;}

}op;

void print(int x){

	if(x==t-1)return;

	int sz=G[x+1].size();

	for(int i=0;i<sz;++i){

		int e=G[x+1][i];

		if(e%2==0&&edges[e].cap==0&&!viss[e]){

			print(edges[e].to);

			cout<<A[x]<<endl;

			return;

		}

	}

}

int main(){

	int N,M;cin>>N>>M;

	int cnt=1;

	for(int i=1;i<=N;++i){

		string s;cin>>s;idx[s]=cnt;A[cnt]=s;

		if(i==1||i==N)op.addedge(cnt,cnt+1,2,0);

		else op.addedge(cnt,cnt+1,1,0);

		cnt+=2;

	}

	n=cnt-1,s=1,t=n;

	for(int i=1;i<=M;++i)

	{

          string a,b;cin>>a>>b;

          int ax=idx[a],bx=idx[b];

          if(ax<bx)op.addedge(ax+1,bx,1,-1);

          else op.addedge(bx+1,ax,1,-1);

	}

     int F=op.maxflow();

     ll ans=op.getcost();

     if(F!=2)

     {

         if(ans==-1){

         	   cout<<2<<endl;

         	   cout<<A[s]<<endl;

         	   cout<<A[t-1]<<endl;

         	   cout<<A[s]<<endl;

         	   return 0;

         }

         else {cout<<"No Solution!"<<endl;return 0;}

     }

     cout<<-ans<<endl;

     int tr=s;

     cout<<A[s]<<endl;

     do

     {

        ++tr;

        int sz=G[tr].size();

        for(int i=0;i<sz;++i){

        	int e=G[tr][i];

        	if(e%2==0&&edges[e].cap==0){tr=edges[e].to,viss[e]=1;break;}

        }

        if(tr!=t)cout<<A[tr]<<endl;

     }while(tr!=t);

     print(s);

     return 0;

}