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\n", 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('\n');

        }

    }

}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();

}