网站代理浏览器7,网页qq登录记录网站,互联网app推广,站长统计app软件下载官网安卓洛谷传送门 LOJ传送门 这道题的图还挺好想的吧 反正都是无向边#xff0c;起点走到终点再回到起点#xff0c;就相当于从起点走$2$次到达终点#xff0c;且这两次不经过相同的点#xff0c;还要经过尽可能多的点 很经典的费用流建图 限制点通过次数-拆点连边#xff0…洛谷传送门 LOJ传送门 这道题的图还挺好想的吧 反正都是无向边起点走到终点再回到起点就相当于从起点走$2$次到达终点且这两次不经过相同的点还要经过尽可能多的点 很经典的费用流建图 限制点通过次数-拆点连边流量为$1$费用为$1$ 图中的其他边编号较小的指向编号较大的流量为$inf$费用为$0$ 跑最大费用最大流即可 注意有$1$直接到$n$的情况所以其他边流量要设置到至少大于$2$ 至于输出方案呢在残量网络中每次都$dfs$找出一条从汇点到源点的路径即可 1 #include map2 #include string3 #include cstdio4 #include cstring5 #include iostream6 #include algorithm7 #define N1 2108 #define M1 400109 #define ll long long10 #define dd double11 #define inf 0x3f3f3f3f12 using namespace std;13 14 int gint()15 {16 int ret0,fh1;char cgetchar();17 while(c0||c9){if(c-)fh-1;cgetchar();}18 while(c0c9){retret*10c-0;cgetchar();}19 return ret*fh;20 }21 struct Edge{22 int head[N1],to[M11],nxt[M11],flow[M11],cost[M11],cte;23 void ae(int u,int v,int F,int C)24 {25 cte; to[cte]v; flow[cte]F; cost[cte]C;26 nxt[cte]head[u]; head[u]cte;27 }28 }e,E;29 int n,m,nn,S,T;30 mapstring,intmp;31 int que[M1],hd,tl,cost[N1],flow[N1],id[N1],use[N1];32 int spfa()33 {34 int x,j,v;35 memset(flow,0,sizeof(flow));36 for(jS;jT;j) cost[j]-inf;37 hd1,tl0; que[tl]S; cost[S]0; flow[S]inf; use[S]1;38 while(hdtl)39 {40 xque[hd];41 for(je.head[x];j;je.nxt[j])42 {43 ve.to[j];44 if( cost[v]cost[x]e.cost[j] e.flow[j]0 )45 {46 cost[v]cost[x]e.cost[j]; id[v]j;47 flow[v]min(flow[x],e.flow[j]);48 if(!use[v]) que[tl]v, use[v]1;49 }50 }51 use[x]0;52 }53 return cost[T]!-inf;54 }55 int stk[N1],tp;56 void dfs(int x)57 {58 int j,v;59 if(xn) stk[tp]x;60 if(x1) return;61 for(je.head[x];j;je.nxt[j])62 {63 ve.to[j];64 if(!e.flow[j]) continue;65 if(xn){66 if(vx-n)67 { e.flow[j]--; dfs(v); break; }68 }else{69 if(vxn)70 { e.flow[j]--; dfs(v); break; }71 }72 }73 }74 char str[N1][20];75 void EK()76 {77 int x,tcost0,mxflow0,i,len,j;78 while(spfa())79 {80 mxflowflow[T]; tcostflow[T]*cost[T];81 for(xT;x!S;xe.to[id[x]^1])82 {83 e.flow[id[x]]-flow[T];84 e.flow[id[x]^1]flow[T];85 }86 }87 if(mxflow2){ puts(No Solution!); return; }88 printf(%d\n,tcost-2);89 dfs(nn); 90 while(tp) 91 {92 xstk[tp]; lenstrlen(str[x]);93 for(j0;jlen;j) printf(%c,str[x][j]);94 puts(); tp--;95 }96 dfs(nn); 97 for(i2;itp;i)98 {99 xstk[i]; lenstrlen(str[x]);
100 for(j0;jlen;j) printf(%c,str[x][j]);
101 puts();
102 }
103 }
104 int main()
105 {
106 scanf(%d%d,n,m);
107 string s;int i,j,x,y,len;
108 nnnn; S0; Tnn1; e.cte1;
109 for(i1;in;i)
110 {
111 cins; mp[s]i; lens.length();
112 for(j0;jlen;j)
113 str[i][j]s[j];
114 }
115 e.ae(1,1n,2,1); e.ae(1n,1,0,-1);
116 e.ae(n,nn,2,1); e.ae(nn,n,0,-1);
117 for(i2;in;i) e.ae(i,in,1,1), e.ae(in,i,0,-1);
118 for(i1;im;i)
119 {
120 cins; xmp[s]; cins; ymp[s];
121 if(xy) swap(x,y);
122 e.ae(xn,y,2,0); e.ae(y,xn,0,0);
123 }
124 e.ae(S,1,2,0); e.ae(1,S,0,0);
125 e.ae(nn,T,2,0); e.ae(T,nn,0,0);
126 EK();
127 return 0;
128 } 转载于:https://www.cnblogs.com/guapisolo/p/10295888.html
