Solution
这题实际上并不是构造题, 而是一道网络流.
我们考虑题目要求的一条路径应该是什么样子的: 它是一个环, 并且满足每个点有且仅有一条出边, 一条入边, 同时这两条边的权值还必须不一样.
考虑如何建图: 我们对每个景点分别建一个点, 源点连向左岸的景点, 右岸的景点连向汇点, 边的容量都是2, 这限制了一个点最多只能连两条边; 我们再将一个点拆成(k)个, 每个代表一个连入的边的权值, 也就是说对于连入一个点的所有边, 都连在代表该边的权值的点上; 一个景点与其拆成的(k)个点之间的边容量为(1), 也就限制了相邻两条边的权值必定不相同. 考虑一个最大流的情况, 就相当于使得每个景点都连满两条边, 又由于题目保证有解, 因此在图上乱搞输出答案即可.
乱搞比较麻烦, 写的时候也比较急躁, 因此变量名比较奇怪不要细究.
注意建图时候的反向边容量为(0)啦.
#include <cstdio>
#include <cctype>
#include <deque>
#include <algorithm>
#include <cstring>
#define deque std::deque
#define min std::min
namespace Zeonfai
{
inline int getInt()
{
int a = 0, sgn = 1; char c;
while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;
while(isdigit(c)) a = a * 10 + c - '0', c = getchar();
return a * sgn;
}
}
const int INF = (int)1e9;
int n, K;
int S, T;
int id[2][50][6], idx[(int)1e6];
struct graph
{
struct edge
{
int v, w, nxt;
}edg[(int)1e6];
int tp, hd[(int)1e6], dep[(int)1e6], vst[(int)1e6];
inline graph() {tp = 0; memset(hd, -1, sizeof(hd));}
inline void addEdge(int u, int v, int w)
{
edg[tp].v = v; edg[tp].w = w; edg[tp].nxt = hd[u]; hd[u] = tp ++;
edg[tp].v = u; edg[tp].w = 0; edg[tp].nxt = hd[v]; hd[v] = tp ++; // 注意反向边的权值
}
inline int BFS()
{
deque<int> que; que.clear();
memset(dep, -1, sizeof(dep));
dep[S] = 0; que.push_back(S);
for(; ! que.empty(); que.pop_front())
{
int u = que.front();
if(u == T) return 1;
for(int p = hd[u]; ~ p; p = edg[p].nxt) if(edg[p].w && dep[edg[p].v] == -1) dep[edg[p].v] = dep[u] + 1, que.push_back(edg[p].v);
}
return 0;
}
int DFS(int u, int flw)
{
if(u == T) return flw;
int flowSum = 0;
for(int p = hd[u]; ~ p; p = edg[p].nxt) if(edg[p].w && dep[edg[p].v] == dep[u] + 1)
{
int currentFlow = DFS(edg[p].v, min(flw - flowSum, edg[p].w));
edg[p].w -= currentFlow; edg[p ^ 1].w += currentFlow;
flowSum += currentFlow;
if(flowSum == flw) return flowSum;
}
if(! flowSum) dep[u] = -1;
return flowSum;
}
inline void dinic()
{
while(BFS()) DFS(S, INF);
}
int cnt;
int ans[(int)1e6];
void getAnswer(int u)
{
vst[u] = 1; ans[cnt ++] = idx[u];
for(int p = hd[u]; ~ p; p = edg[p].nxt) if(! edg[p].w && ! vst[edg[p].v]) getAnswer(edg[p].v);
}
inline void getAnswer()
{
memset(vst, 0, sizeof(vst)); int lnk[51][2]; int ans[51][51]; int cxxt[51];
memset(ans, -1, sizeof(ans));
for(int i = 1; i <= n; ++ i)
{
int cnt = 0;
for(int j = 1; j <= K; ++ j) for(int p = hd[id[0][i][j]]; ~ p; p = edg[p].nxt) if(edg[p].v != id[0][i][0] && ! edg[p].w) lnk[i][cnt ++] = idx[edg[p].v];
}
int fxxk = 0;
for(int i = 1; i <= n; ++ i) if(! vst[i])
{
int tmp[51], cnt = 2; tmp[0] = i; tmp[1] = lnk[i][0]; vst[i] = 1;
while(1)
{
int flg = 0;
for(int j = 1; j <= n; ++ j) if(! vst[j] && (lnk[j][0] == tmp[cnt - 1] || lnk[j][1] == tmp[cnt - 1]))
{
flg = 1;
vst[j] = 1;
int dxmn = tmp[cnt - 1] ^ lnk[j][0] ^ lnk[j][1];
tmp[cnt ++] = j; tmp[cnt ++] = dxmn;
break;
}
if(! flg) break;
}
tmp[cnt ++] = i;
for(int j = 0; j < cnt; ++ j) ans[fxxk][j] = tmp[j];
cxxt[fxxk ++] = cnt;
}
printf("%d
", fxxk);
for(int i = 0; i < fxxk; ++ i)
{
printf("%d ", cxxt[i]);
for(int j = 0; j < cxxt[i]; ++ j) putchar(j % 2 == 0 ? 'L' : 'R'), printf("%d ", ans[i][j]);
putchar('
');
}
}
}G;
int main()
{
#ifndef ONLINE_JUDGE
freopen("river.in", "r", stdin);
freopen("river.out", "w", stdout);
#endif
using namespace Zeonfai;
n = getInt(); int m = getInt(); K = getInt();
int cnt = 0;
for(int i = 0; i < 2; ++ i) for(int j = 1; j <= n; ++ j) for(int k = 0; k <= K; ++ k) id[i][j][k] = cnt, idx[cnt++] = j;
S = cnt ++; T = cnt ++;
for(int i = 0; i < m; ++ i)
{
int u = getInt(), v = getInt(), k = getInt();
G.addEdge(id[0][u][k], id[1][v][k], 1);
}
for(int i = 1; i <= n; ++ i)
{
G.addEdge(S, id[0][i][0], 2);
for(int j = 1; j <= K; ++ j) G.addEdge(id[0][i][0], id[0][i][j], 1);
}
for(int i = 1; i <= n; ++ i)
{
G.addEdge(id[1][i][0], T, 2);
for(int j = 1; j <= K; ++ j) G.addEdge(id[1][i][j], id[1][i][0], 1);
}
G.dinic();
G.getAnswer();
}