洛谷P2770 航空路线问题（费用流）-白红宇

洛谷P2770 航空路线问题（费用流）

阅读量：5235 次

发布时间：2019-06-14

本文共 1997 字，大约阅读时间需要 6 分钟。

完了这题好厉害……字符串什么的好麻烦……

要求从$1$到$n$的路径，不重复，经过边数最多

每一个点拆成两个，$A_i,B_i$，然后$A_i$到$B_i$连容量为$1$，费用为$1$的边，保证每个点只被选一次

然后$1$和$n$的话要容量为$2$

然后有连边的话，$B_i$向$A_j$连边，容量$1$，费用$1$

要选的点最多，那么就是要费用最大，所以跑一个最大费用流

然后找方案的话，直接dfs，然后正着和倒着输出

有几个细节，写在代码里了

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
          7 #define inf 0x3f3f3f3f 8 using namespace std; 9 const int N=5005,M=500005;10 int ver[M],Next[M],head[N],edge[M],flow[M],tot=1;11 int dis[N],disf[N],Pre[N],last[N],vis[N],maxflow,maxcost;12 int n,m,s,t;bool check=0;13 queue
          
            q;14 map
           
             mp;15 string name[N];16 inline void add(int u,int v,int f,int e){17 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,flow[tot]=f,edge[tot]=e;18 ver[++tot]=u,Next[tot]=head[v],head[v]=tot,flow[tot]=0,edge[tot]=-e;19 }20 bool spfa(){21 memset(dis,0xef,sizeof(dis));22 q.push(s),dis[s]=0,disf[s]=inf,Pre[t]=-1;23 while(!q.empty()){24 int u=q.front();q.pop();vis[u]=0;25 for(int i=head[u];i;i=Next[i]){26 int v=ver[i];27 if(flow[i]&&dis[v]
            
             =0){51 out(ver[i]);52 flow[i]=1;53 return;54 }55 }56 }57 int main(){58 //freopen("testdata.in","r",stdin);59 string s1,s2;60 scanf("%d%d",&n,&m);61 for(int i=1;i<=n;++i){62 cin>>s1;63 mp[s1]=i;64 name[i]=s1;65 add(i,i+n,1,1);66 }67 for(int i=1;i<=m;++i){68 cin>>s1>>s2;69 int a=mp[s1],b=mp[s2];70 if(a>b) swap(a,b);71 if(a==1&&b==n) check=1;72 add(a+n,b,1,1);73 }74 add(1,n+1,1,1),add(n,n+n,1,1);75 s=1,t=n+n;76 dinic();77 if(!maxflow||(maxflow==1&&!check)) return puts("No Solution!"),0;78 if(maxflow==1&&check){cout<<2<<'\n'<
             
              <<'\n'<
              
               <<'\n'<
               
                <<'\n';return 0;}79 printf("%d\n",maxcost/2-1);80 //这里的最多城市数是这个81 //因为考虑如果边连成一个环，边数等于点数82 //然后每个点拆成两个，除以二83 //然后因为s'和t'被重复了两次，减去1 84 out(s);85 for(int i=1;i<=num;++i) if(ans[i]<=n) cout<
                
                 <<'\n';86 num=0;87 out(s);88 for(int i=num-2;i;--i) if(ans[i]<=n) cout<
                 
                  <<'\n';89 //最后两个肯定是t和t'，不用管 90 return 0;91 }