首页 > 代码库 > URAL 2089 Experienced coach Twosat
URAL 2089 Experienced coach Twosat
Description
Misha trains several ACM teams at the university. He is an experienced coach, and he does not underestimate the meaning of friendly and collaborative atmosphere during training sessions. It used to be that way, but one of the teams happened to win contests a little bit more often than others, and hence became slightly too big for their boots. That does not contribute to positive spirit which is essential for successful training. But Misha knows what to do!
Representatives of k teams participate in Misha’s training sessions, each team has three members. Alas, teams rarely attend en masse, but at least one member per team is always present, of course. During the next training session Misha is going to split everyone into npairs, so that each pair will include representatives of different teams. Players will play a mini-contest against each other in each pair.
A situation when no two mini-contests are won by representatives of one team is the one that suits Misha’s goals best. He may be somewhat cunning when selecting winner in each pair in order to achieve such situation. Find out whether Misha will succeed.
Input
The first line contains two numbers — n and k (1 ≤ n ≤ 10 5, 2 ≤ k ≤ 10 5). n lines follow. i-th of these contains two numbers x i, y i (1 ≤ x i, y i ≤ k; x i ≠ y i) — the numbers of teams, whose representatives are in pair number i.
It is guaranteed that each team is represented in no less than one and no more than three pairs.
Output
If Misha is to succeed, output Yes in the first line. In each of the following n lines output one number — the number of team that is to win in the corresponding pair. If there are several answers, output any.
If Misha is to fail, output No in the only line.
Sample Input
| input | output |
|---|---|
3 41 22 31 4 | Yes234 |
6 41 21 31 42 32 43 4 | No |
题意：给出n对点a,b 要求从没对点中选出一个，且最终选出的点n个数不能存在相同的。输入数据满足每种数最多出现3次，最少出现1次
思路：第i对点的编号2*i， 2*i+1, 因为每个数最多出现3次,那么完全可以枚举每个数，然后相同的数之间的编号连一条边，表示这两个编号不能同时选，这样跑完twosat就能得到一个满足情况的解或无解。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <queue>#include <stack>#include <cstdlib>#include <map>#include <set>#include <cmath>using namespace std;const int N = 2e6 + 100;struct Edge { int to, nex;}e[N];int head[N], tot;void init() { tot = 0; memset(head, -1, sizeof head);}void add(int u, int v) { e[tot].to = v; e[tot].nex = head[u]; head[u] = tot++;}int Low[N], DFN[N], Stack[N], Belong[N];int Index, top;int scc;bool Instack[N];int num[N];void Tarjan(int u) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u]; ~i; i = e[i].nex) { v = e[i].to; if(!DFN[v]) { Tarjan(v); if(Low[u] > Low[v]) Low[u] = Low[v]; }else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { scc++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = scc; num[scc]++; }while(v != u); }}bool solvable(int n) { memset(DFN, 0, sizeof DFN); memset(Instack, false, sizeof Instack); memset(num, 0, sizeof num); Index = scc = top = 0; for(int i = 0; i < n; ++i) if(!DFN[i]) Tarjan(i); for(int i = 0; i < n; i += 2) { if(Belong[i] == Belong[i ^ 1]) return false; } return true;}queue<int> q1, q2;vector<vector<int> >dag;int vis[N];int indeg[N];int cf[N];void solve(int n) { dag.assign(scc+1, vector<int>()); memset(indeg, 0, sizeof indeg); memset(vis, 0, sizeof vis); for(int u = 0; u < n; ++u) { for(int i = head[u]; ~i; i = e[i].nex) { int v = e[i].to; if(Belong[u] != Belong[v]) { dag[ Belong[v] ].push_back(Belong[u]); indeg[ Belong[u] ]++; } } } for(int i = 0; i < n; i += 2) { cf[ Belong[i] ] = Belong[i ^ 1]; cf[ Belong[i ^ 1] ] = Belong[i]; } while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop(); for(int i = 1; i <= scc; ++i) if(indeg[i] == 0) q1.push(i); while(!q1.empty()) { int u = q1.front(); q1.pop(); if(vis[u] == 0) { vis[u] = 1; vis[ cf[u] ] = 0; } int sz = dag[u].size(); for(int i = 0; i < sz; ++i) { indeg[ dag[u][i] ]--; if(indeg[ dag[u][i] ] == 0) q1.push(dag[u][i]); } }}int r[N];vector<int> g[N];int main() {#ifdef LOCAL freopen("in", "r", stdin);#endif int n, m; while(~scanf("%d%d", &m, &n)) { init(); int tot = 0; int u, v; for(int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); r[tot++] = u; r[tot++] = v; g[u].push_back(2 * i); g[v].push_back(2 * i + 1); } for(int i = 1; i <= n; ++i) { int sx = g[i].size(); for(int j1 = 0; j1 < sx; ++j1) { for(int j2 = j1 + 1; j2 < sx; ++j2) { int v1 = g[i][j1]; int v2 = g[i][j2]; add(v1, v2 ^ 1); add(v2, v1 ^ 1); } } } if(solvable(2 * m)) { solve(2 * m); puts("Yes"); for(int i = 0; i < m; ++i) { if(vis[ Belong[2 * i] ]) printf("%d\n", r[2 * i + 1]); else printf("%d\n", r[2 * i]); } }else puts("No"); } return 0;}
URAL 2089 Experienced coach Twosat
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。