【题解】航空路线问题

叁歲伎倆 2021-11-18 01:18 268阅读 0赞

## 航空路线问题 ##

一个点有两种用法，但是只能选一种用，直接把一个点拆掉并且连一条容量为1的边就成功限制。

将一个点拆为两个点，一个入点一个出点，入点到出点连一条费用为\\(-inf\\) 的边，跑费用流，最终答案就是  
\\\[ -\\dfrac \{cost\} \{inf\} \\\]

输出方案随便弄一下就好了。注意考虑边界情况！！！(1-》n)，(不连通)

强行总结：将一个状态点拆成两个点，中间用一条边来限制，可以模拟一个一个点只有两种状态的图，更多状态甚至都可以。

费用流不能跑负环。spfa能跑什么费用流就可以跑什么。

//@winlere #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<vector> using namespace std; typedef long long ll; inline int qr(){ register int ret=0,f=0; register char c=getchar(); while(c<48||c>57)f|=c==45,c=getchar(); while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar(); return f?-ret:ret; } struct E{ int to,nx,w,c; E(){to=nx=w=c=0;} E(const int&a,const int&b,const int&CX,const int&d){to=a;nx=b;w=CX;c=d;} }e[30005]; int head[404]; int cnt=1; inline void add(const int&fr,const int&to,const int&w,const int&c,const bool&f){ e[++cnt]=E(to,head[fr],w,c); head[fr]=cnt; //printf("fr=%d to=%d w=%d c=%d cnt=%d\n",fr,to,w,c,cnt); if(f)add(to,fr,0,-c,0); } const int maxn=505; int d[maxn]; int fl[maxn]; int in[maxn]; int last[maxn]; int S,T,n,v,cost; const int inf=0x3f3f3f3; const int littleinf=1; queue < int > q; void mincost(){ while(1){ for(register int t=1;t<=T;++t) d[t]=inf,fl[t]=0,last[t]=0,in[t]=0; d[S]=0;fl[S]=inf; q.push(S); while(!q.empty()){ register int now=q.front(); q.pop(); in[now]=0; //cout<<now<<endl; for(register int t=head[now];t;t=e[t].nx){ //cout<<t<<endl; if(d[e[t].to]>e[t].c+d[now]&&e[t].w>0){ d[e[t].to]=e[t].c+d[now]; if(!in[e[t].to]) q.push(e[t].to); in[e[t].to]=1; fl[e[t].to]=min(e[t].w,fl[now]); last[e[t].to]=t; } } } if(fl[T]<=0)return; cost-=fl[T]*d[T]; for(register int t=T;t!=S;t=e[last[t]^1].to) e[last[t]].w-=fl[T],e[last[t]^1].w+=fl[T]; } } vector < int > ve,VE; map < string , int > name; map < int , string > arc; int main(){ freopen("airl.in","r",stdin); freopen("airl.out","w",stdout); n=qr();v=qr(); for(register int t=1;t<=n;++t){ string f; cin>>f; name[f]=t; arc[t]=f; add(t+1,t+n+1,1+(t==1||t==n),0,1); } for(register int t=1;t<=v;++t){ string t1,t2; cin>>t1>>t2; int i1,i2; i1=name[t1];i2=name[t2]; if(i1>i2)swap(i1,i2); add(i1+n+1,i2+1,1+(i1==1&&i2==n),-1,1); } S=1; T=n+n+2; add(n+n+1,T,2,0,1); add(S,2,2,0,1); mincost(); if(e[cnt].w!=2) return puts("No Solution!"),0; printf("%d\n",cost); int now=1; ve.push_back(now); while(now!=n){ for(register int t=head[now+n+1];t;t=e[t].nx){ if(e[t^1].w&&e[t].to>1&&e[t].to<=n+1&&!in[e[t].to-1]){ now=e[t].to-1; break; } } in[now]=1; ve.push_back(now); } in[n]=0; now=1; while(now!=n){ int f=1; for(register int t=head[now+n+1];t;t=e[t].nx){ if(e[t^1].w&&e[t].to>1&&e[t].to<=n+1&&!in[e[t].to-1]){ now=e[t].to-1; f=0; break; } } if(now==n||f)break; in[now]=1; VE.push_back(now); } reverse(VE.begin(),VE.end()); VE.push_back(1); for(vector< int >::iterator t=ve.begin();t!=ve.end();++t) cout<<arc[*t]<<endl; for(vector< int >::iterator t=VE.begin();t!=VE.end();++t) cout<<arc[*t]<<endl; return 0; }

转载于:https://www.cnblogs.com/winlere/p/11234628.html