題目描述

題解：

相當于找兩條起點到終點的路徑。

所以拆點后只有起點和終點的$x$和$y$之間容量為$2$，其余為$1$。

直接最大費用流即可。

代碼：

#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 150 #define seed 499139 #define ll long long #define ull unsigned long long const int inf = 0x3f3f3f3f; const ll Inf = 0x3f3f3f3f3f3f3f3fll; inline int rd() {int f=1,c=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}return f*c; } int n,m,S,T,hed[N<<1],cnt=-1; char ch[N][20],a[20],b[20]; ull hs[N]; ull get_hs(char *c,int len) {ull ret = 0;for(int i=1;i<=len;i++)ret=ret*seed+c[i];return ret; } int fd(ull hsh) {for(int i=1;i<=n;i++)if(hs[i]==hsh)return i;return -1; } struct EG {int to,nxt;ll w,c; }e[N*N*2]; void ae(int f,int t,ll w,ll c) {e[++cnt].to = t;e[cnt].nxt = hed[f];e[cnt].w = w;e[cnt].c = c;hed[f] = cnt; } ll dep[N],fl[N]; int pre[N],fa[N]; bool vis[N]; queue<int>q; bool spfa() {memset(dep,0x3f,sizeof(dep));dep[S]=0,fl[S]=Inf,vis[S]=1;q.push(S);while(!q.empty()){int u = q.front();q.pop();for(int j=hed[u];~j;j=e[j].nxt){int to = e[j].to;if(e[j].w&&dep[to]>dep[u]+e[j].c){dep[to] = dep[u]+e[j].c;fl[to] = min(fl[u],e[j].w);pre[to] = j,fa[to] = u;if(!vis[to]){vis[to]=1;q.push(to);}}}vis[u] = 0;}return dep[T]!=Inf; } ll mc,mf;void mcmf() {while(spfa()){mc+=fl[T]*dep[T];mf+=fl[T];int u = T;while(u!=S){e[pre[u]].w-=fl[T];e[pre[u]^1].w+=fl[T];u = fa[u];}} } bool ck() {if(mf==1){for(int j=hed[2];~j;j=e[j].nxt)if(e[j].to==(n<<1|1))return 1;}return 0; } int sta[N<<1],tl; void print(int u) {sta[++tl]=(u>>1);if((u>>1)==1)return ;for(int j=hed[u];~j;j=e[j].nxt){int to = e[j].to;if(to&1)continue;if(!e[j].w)continue;print(to+1);} } int main() {n = rd(),m = rd();S = 0,T = 1;memset(hed,-1,sizeof(hed));for(int i=1;i<=n;i++){scanf("%s",ch[i]+1);int len = strlen(ch[i]+1);hs[i] = get_hs(ch[i],len);}ae(S,3,2,0);ae(3,S,0,0);ae(n<<1,T,2,0);ae(T,n<<1,0,0);ae(3,2,2,0);ae(2,3,0,0);ae(n<<1|1,n<<1,2,0);ae(n<<1,n<<1|1,0,0);for(int i=2;i<n;i++){ae(i<<1|1,i<<1,1,0);ae(i<<1,i<<1|1,0,0);}for(int f,t,i=1;i<=m;i++){scanf("%s%s",a+1,b+1);f = fd(get_hs(a,strlen(a+1)));t = fd(get_hs(b,strlen(b+1)));if(f>t)f^=t^=f^=t;ae(f<<1,t<<1|1,1,-1);ae(t<<1|1,f<<1,0,1);}mcmf();if(mf==2){printf("%lld\n",-mc);print(n<<1|1);for(int i=tl;i>=1;i--){if(i!=tl&&sta[i]==1){for(int j=1;j<=i;j++)printf("%s\n",ch[sta[j]]+1);break;}printf("%s\n",ch[sta[i]]+1);}}else{if(ck()){printf("2\n%s\n%s\n%s\n",ch[1]+1,ch[n]+1,ch[1]+1);}else puts("No Solution!");}return 0; }

?

轉載于:https://www.cnblogs.com/LiGuanlin1124/p/10256441.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的航空路线问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。