?

HINT

?

注意是全程不能經(jīng)過兩個(gè)相同的景點(diǎn)，并且一天的開始和結(jié)束不能用同樣的交通方式。

?

?

[吐槽]

　　嗯。。看到這題的想法的話。。先想到了每個(gè)點(diǎn)的度為2，然后就有點(diǎn)不知所措了

　　隱隱約約想到了網(wǎng)絡(luò)流，但并沒有繼續(xù)往下想了。。。

　　聽完學(xué)長的講評之后（%xj）個(gè)人覺得建圖還是很有意思的ovo

[題解]

　　因?yàn)槊總€(gè)點(diǎn)到對面都有k種方式，那就想到每個(gè)點(diǎn)原來的點(diǎn)$x_0$拆成k個(gè)點(diǎn)$x_1$, $x_2$, $x_3$... $x_k$

　　然后很自然地$x_0$和拆成的點(diǎn)之間要連邊

　　容量的話，因?yàn)閔int里面的限制，也就是說一個(gè)點(diǎn)到另一個(gè)點(diǎn)的k中交通方式中只能選一種

　　（因?yàn)槊總€(gè)點(diǎn)只能到一次，而開始和結(jié)束不能用同樣的方式）

　　這樣一來容量顯然就應(yīng)該是1了

　　兩岸之間的連接，就直接按照讀入左岸連到右岸就好，容量也為1

　　（但其實(shí)因?yàn)樽蟀兜牧魅肓髁亢陀野兜牧鞒隽髁慷加邢拗?#xff0c;中間的那條好像容量取1~ $\infty$都可以。。。%yxq）

?

　　接著考慮最后的答案是怎么得到的，會(huì)發(fā)現(xiàn)其實(shí)我們最后的到的路線是若干個(gè)環(huán)，每個(gè)點(diǎn)的度為2（一個(gè)大概長這樣的）

　　

?

?

　　如此一來，就會(huì)有個(gè)大膽的想法

　　對于每一個(gè)左岸的$x_0$，我們連一條源點(diǎn)到它的容量為2的邊

　　對于每一個(gè)右岸的$x_0$，我們連一條它到匯點(diǎn)的容量為2的邊

　　這樣起到一個(gè)限制了每個(gè)點(diǎn)的度的作用，就可以保證有環(huán)并且環(huán)內(nèi)每個(gè)點(diǎn)的度都為2（個(gè)人感覺這點(diǎn)是很有意思的）

　　

　　于是乎最終的到的圖長這樣（以樣例為例）

　　

?

?

　　那么現(xiàn)在考慮構(gòu)造方案

　　看回之前建圖的思路，很容易得到的一個(gè)結(jié)論是滿流的邊肯定就是要走的邊

　　那么現(xiàn)在問題就變成知道一堆邊然后構(gòu)造方案啦

　　很簡單粗暴的方法直接強(qiáng)行把每個(gè)環(huán)走一遍記錄下答案就好

　　天數(shù)的話就看有多少個(gè)環(huán)就好啦

?

　　挫挫的代碼qwq

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #define inf 2147483647 6 using namespace std; 7 const int MAXN=50*6*2+10; 8 struct xxx 9 { 10 int y,next,op,r,x; 11 }a[MAXN*2]; 12 queue<int> q; 13 int h[MAXN],lv[MAXN],id[110][10],num[MAXN]; 14 int go[MAXN][2],ans[110][110]; 15 bool vis[MAXN]; 16 int n,m,k,vs,vt,tot,tot1; 17 int add(int x,int y,int r); 18 int bfs(); 19 int dfs(int v,int o); 20 int get_ans(); 21 22 int main() 23 { 24 freopen("a.in","r",stdin); 25 26 int x,y,z; 27 scanf("%d%d%d",&n,&m,&k); 28 memset(h,-1,sizeof(h)); 29 tot=0; 30 vs=0,vt=MAXN-1; 31 for (int i=1;i<=n+n;++i) 32 for (int j=0;j<=k;++j) 33 id[i][j]=++tot,num[tot]=i; 34 tot=0; 35 for (int i=1;i<=n;++i) 36 { 37 add(vs,id[i][0],2); 38 add(id[i+n][0],vt,2); 39 for (int j=1;j<=k;++j) 40 add(id[i][0],id[i][j],1),add(id[i+n][j],id[i+n][0],1); 41 } 42 for (int i=1;i<=m;++i) 43 { 44 scanf("%d%d%d",&x,&y,&z); 45 add(id[x][z],id[y+n][z],1); 46 } 47 while (bfs()) dfs(vs,inf); 48 get_ans(); 49 } 50 51 int add(int x,int y,int r) 52 { 53 a[++tot].y=y; a[tot].next=h[x]; h[x]=tot; a[tot].r=r; a[tot].op=tot+1; 54 a[++tot].y=x; a[tot].next=h[y]; h[y]=tot; a[tot].r=0; a[tot].op=tot-1; 55 } 56 57 int bfs() 58 { 59 while (!q.empty()) q.pop(); 60 memset(lv,0,sizeof(lv)); 61 q.push(vs); 62 lv[vs]=1; 63 int v,u; 64 while (!q.empty()) 65 { 66 v=q.front(); q.pop(); 67 for (int i=h[v];i!=-1;i=a[i].next) 68 { 69 u=a[i].y; 70 if (lv[u]||!a[i].r) continue; 71 q.push(u); 72 lv[u]=lv[v]+1; 73 if (u==vt) return true; 74 } 75 } 76 return false; 77 } 78 79 int dfs(int v,int o) 80 { 81 if (v==vt||o==0) return o; 82 int u,flow,ret=0; 83 for (int i=h[v];i!=-1;i=a[i].next) 84 { 85 u=a[i].y; 86 if (lv[u]!=lv[v]+1) continue; 87 flow=dfs(u,min(a[i].r,o)); 88 if (flow) 89 { 90 a[i].r-=flow; 91 a[a[i].op].r+=flow; 92 ret+=flow; 93 o-=flow; 94 if (!o) break; 95 } 96 } 97 return ret; 98 } 99 100 int get_ans() 101 { 102 int x,y,pre; 103 //go[i]記錄與i相連的兩個(gè)點(diǎn) 104 for (int i=1;i<=n;++i) 105 for (int j=1;j<=k;++j) 106 for (int tmp=h[id[i][j]];tmp!=-1;tmp=a[tmp].next) 107 { 108 if (a[tmp].r||a[tmp].y==id[i][0]) continue; 109 y=num[a[tmp].y]; 110 if (!go[i][0]) go[i][0]=y; 111 else go[i][1]=y; 112 113 if (!go[y][0]) go[y][0]=i; 114 else go[y][1]=i; 115 } 116 memset(vis,false,sizeof(vis)); 117 int cnt=0; 118 for (int i=1;i<=n;++i) 119 { 120 if (vis[i]) continue; 121 ++cnt; 122 //將每個(gè)環(huán)走一遍 123 pre=i,x=go[i][0]; 124 ans[cnt][++ans[cnt][0]]=i; 125 vis[i]=true; 126 while (x!=i) 127 { 128 vis[x]=true; 129 ans[cnt][++ans[cnt][0]]=x; 130 if (pre==go[x][0]) pre=x,x=go[x][1]; 131 else pre=x,x=go[x][0]; 132 } 133 ans[cnt][++ans[cnt][0]]=x; 134 } 135 printf("%d\n",cnt); 136 //因?yàn)榻▓D的方式所以左右岸肯定是交錯(cuò)來的 137 for (int i=1;i<=cnt;++i) 138 { 139 printf("%d ",ans[i][0]); 140 for (int j=1;j<=ans[i][0];++j) 141 if (j&1) printf("L%d ",ans[i][j]); 142 else printf("R%d ",ans[i][j]-n); 143 printf("\n"); 144 } 145 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/yoyoball/p/7451306.html

總結(jié)

以上是生活随笔為你收集整理的【2016北京集训测试赛】river的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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