hdu 4781 Assignment For Princess(构造)

2019-04-14 19:37发布

站内文章 / 模拟电子
17277 0 982
题目链接：hdu 4781 Assignment For Princess

解题思路

将N个点分成三份，集合1到2的边权模3为1，集合2到3的边权模3为2，3到1为0。然后保证每个点出入度至少为1即可。

代码

#include #include #include #include using namespace std; const int maxn = 105; int N, M, P[3], S[3]; bool vis[maxn][maxn]; vector<int> G[3]; bool solve (int u, int v) { for (int i = 1; i <= S[v]; i++) { int vv = (P[v] + i) % S[v]; int a = G[u][P[u]], b = G[v][vv]; if (vis[a][b]) continue; vis[a][b] = true; P[v] = vv; return true; } return false; } int main () { int cas; scanf("%d", &cas); for (int kcas = 1; kcas <= cas; kcas++) { scanf("%d%d", &N, &M); printf("Case #%d: ", kcas); for (int i = 0; i < 3; i++) G[i].clear(); for (int i = 1; i <= N; i++) G[(i-1)%3].push_back(i); for (int i = 0; i < 3; i++) S[i] = G[i].size(); P[0] = 0, P[1] = P[2] = -1; memset(vis, false, sizeof(vis)); for (int i = 0; i < M; i++) { int u = i % 3, v = (i + 1) % 3; while (!solve(u, v)) P[u] = (P[u] + 1) % S[u]; printf("%d %d %d ", G[u][P[u]], G[v][P[v]], i + 1); } } return 0; }

热门文章