Light oj 1251 - Forming the Council 【2-sat】【推断是否存在可行解 + 反向拓扑输出可行解】
problem=1251" style="color:rgb(79,107,114)"> |
PDF (English) | problem=1251" style="color:rgb(79,107,114)">Statistics |
problem=1251" style="color:rgb(79,107,114)">Forum |
Time Limit: 2 second(s) | Memory Limit: 32 MB |
In a city there are n voters, and m people formed the Govt. council. The council members are numbered from 1 to m. Now everyone is complaining that the council is biased. So, they made a
plan. The plan is that the voters are given a chance to vote again to form the new council. A vote will be like ±i ±j. '+' means the voter wants that member to be in the council, '-' means the voter doesn't
want the member to be in the council. For example, there are 4 voters, they voted like
+1 -3 the voter wants member 1 to be kept in the council or member 3 to be thrown out
+2 +3 the voter wants member 2 to be kept in the council or member 3 to be kept in the council
-1 -2 the voter wants member 1 to be thrown out or member 2 to be thrown out
-4 +1 the voter wants member 4 to be thrown out or member 1 to be kept in the council
A voter will be satisfied if at least one of his wishes becomes true. Now your task is to form the council such that all the voters are happy.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 20000) and m (1 ≤ m ≤ 8000). Each of the next n lines contains a vote in the form ±i ±j (1 ≤ i, j ≤ m).
Output
For each case, print the case number and 'Yes' if a solution exists, or 'No' if there is no solution. Then if the result is yes, print another line containing the number of members in the council followed by the members
in ascending order. And print a single space between two numbers. There can be many solutions. Any valid one will do.
Sample Input |
Output for Sample Input |
3 4 3 +1 +3 +2 -1 +2 -3 -1 -2 4 2 +1 -2 +1 +2 -1 -2 -1 +2 1 3 +1 -3 |
Case 1: Yes 2 2 3 Case 2: No Case 3: Yes 0 |
Note
This is a special judge problem. Wrong output format may cause wrong answer.
如今要建立一个新的理事会,
存在输出Yes,在下一行输出选择的公民总数 并输出被选择公民的编号。
addEdge(i + N, j);// i 离开 那么 j 必然留下
addEdge(i + N, j + N);// i 离开 j 必然离开
addEdge(i, j);// i 留下 j 必然留下
addEdge(i, j + N);// i 留下 那么 j 必然离开
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#define MAXN 16000+10
#define MAXM 40000+10
using namespace std;
struct Edge
{
int from, to, next;
};
Edge edge[MAXM];
int head[MAXN], edgenum;
int low[MAXN], dfn[MAXN];
int sccno[MAXN], scc_cnt;
int dfs_clock;
stack<int> S;
bool Instack[MAXN];
int N, M;
void init()
{
edgenum = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v)
{
Edge E = {u, v, head[u]};
edge[edgenum] = E;
head[u] = edgenum++;
}
void getMap()
{
int a, b;
while(M--)
{
scanf("%d%d", &a, &b);
if(a > 0 && b > 0)//a 和 b 至少一个留下
{
addEdge(b + N, a);
addEdge(a + N, b);
}
else if(a > 0 && b < 0)//a留 和 b走 至少成立一个
{
b = -b;
addEdge(b, a);
addEdge(a + N, b + N);
}
else if(a < 0 && b > 0)//a走 和 b留 至少成立一个
{
a = -a;
addEdge(b + N, a + N);
addEdge(a, b);
}
else//a 和 b 至少走一个
{
a = -a, b = -b;
addEdge(b, a + N);
addEdge(a, b + N);
}
}
}
void tarjan(int u, int fa)
{
int v;
low[u] = dfn[u] = ++dfs_clock;
S.push(u);
Instack[u] = true;
for(int i = head[u]; i != -1; i = edge[i].next)
{
v = edge[i].to;
if(!dfn[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if(Instack[v])
low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
scc_cnt++;
for(;;)
{
v = S.top();S.pop();
Instack[v] = false;
sccno[v] = scc_cnt;
if(v == u) break;
}
}
}
void find_cut(int l, int r)
{
memset(low, 0, sizeof(low));
memset(dfn, 0, sizeof(dfn));
memset(sccno, 0, sizeof(sccno));
memset(Instack, false, sizeof(Instack));
dfs_clock = scc_cnt = 0;
for(int i = l; i <= r; i++)
if(!dfn[i]) tarjan(i, -1);
}
vector<int> G[MAXN];
int in[MAXN];
void suodian()//反向建图
{
for(int i = 1; i <= scc_cnt; i++) G[i].clear(), in[i] = 0;
for(int i = 0; i < edgenum; i++)
{
int u = sccno[edge[i].from];
int v = sccno[edge[i].to];
if(u != v)
G[v].push_back(u), in[u]++;
}
}
int k = 1;
int fp[MAXN];//建立SCC到SCC的映射
int color[MAXN];//染色
void toposort()
{
memset(color, -1, sizeof(color));
queue<int> Q;
for(int i = 1; i <= scc_cnt; i++) if(in[i] == 0) Q.push(i);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
if(color[u] == -1)
{
color[u] = 1;
color[fp[u]] = 0;
}
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(--in[v] == 0)
Q.push(v);
}
}
}
void solve()
{
printf("Case %d: ", k++);
for(int i = 1; i <= N; i++)
{
if(sccno[i] == sccno[i+N])
{
printf("No\n");
return ;
}
else
{
fp[sccno[i]] = sccno[i+N];
fp[sccno[i+N]] = sccno[i];
}
}
printf("Yes\n");
suodian();
toposort();//反向拓扑
int ans = 0;
for(int i = 1; i <= N; i++)
{
if(color[sccno[i]] == 1)
ans++;
}
printf("%d", ans);
for(int i = 1; i <= N; i++)
{
if(color[sccno[i]] == 1)
printf(" %d", i);
}
printf("\n");
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &M, &N);
init();
getMap();
find_cut(1, 2*N);
solve();
}
return 0;
}
最新文章
- 编写jquery常用插件的基本格式
- ThinkPHP 学习笔记 ( 四 ) 数据库操作之关联模型 ( RelationMondel ) 和高级模型 ( AdvModel )
- Android——GridLayout
- oracle 树形SQL
- 码农谷 球从M米高度自由下落第N次落地时反弹的高度
- 二分图匹配 分类: ACM TYPE 2014-10-01 19:57 94人阅读 评论(0) 收藏
- sshd被攻击的自动防御方法v2
- mssql update from
- [Lugu3380]【模板】二逼平衡树(树套树)
- java开源项目之IQQ学习记录之项目环境搭建与启动
- 迷宫-BFS
- C++版 - 剑指Offer 面试题45:圆圈中最后剩下的数字(约瑟夫环问题,ZOJ 1088:System Overload类似)题解
- leetcode98
- linux之用户密码破解的操作
- nginx介绍(六) - 通过反向代理实现跨域访问
- qurtz.net
- Error:svn: E160013 svn主干切换分支时报错
- Prometheus Node_exporter 之 Node Exporter
- Apache的安装与卸载
- Android控件Gridview实现多个menu模块,可添加可删除