|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
題目:http://judge.tnfsh.tn.edu.tw:8080/ShowProblem?problemid=b017
我是用2-SAT做 可是NA 18/27了
覺得可能是字典序的問題 可是我不知道要怎麼改
有人可以幫忙看一下問題在哪裡嗎?m(_ _)m
http://ideone.com/VdWqVn
/**********************************************************************************/
/* Problem: b017 "B.家長會問題" from 2007 校內初選 */
/* Language: C++ */
/* Result: NA (18 / 27) on ZeroJudge */
/* Author: ForTest at 2014-03-25 13:46:24 */
/**********************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <sstream>
using namespace std;
#define F(a,b) for(int a=0;a<b;++a)
typedef long long LL;
const int mv=1000;int cv;
int n,m;
int v[mv],scc[mv];
vector<int>e[mv],be[mv],topo,ans;
int Not(int a){return -a;}
void Add(int a,int b){
e[a].push_back(b);
be[b].push_back(a);
}
void Dfs(vector<int> *E,int x,int tag = -1){
if(v[x])return;
v[x] = 1; scc[x] = tag;
F(i,E[x].size())
Dfs(E, E[x][i], tag);
if(E == e)
topo.push_back(x);
}
void Kos(){
memset(v,0,sizeof v);
for(int i=n+1;i<cv;++i) Dfs(e,i);
for(int i=0;i<n;++i) Dfs(e,i);
memset(v,0,sizeof v);
int cnt = 0;
for(int i=topo.size()-1;i>=0;--i)
Dfs(be,topo[i],cnt++);
}
bool Output(){
for(int i=1+n;i<cv;++i) if(scc[i] == scc[n*2-i]){
puts("0"); return 0;}
printf("%d\n",n);
for(int i=1+n;i<cv;++i)
printf( (scc[i] > scc[n*2-i]) ?
"+" : "-");
puts("");
return 1;
}
int main(){
scanf("%d%d",&n,&m);
cv = n*2 + 1;
F(i,m){
int a,b;
scanf("%d%d",&a,&b);
Add(Not(a)+n,b+n);
Add(Not(b)+n,a+n);
}
Kos();
Output();
return 0;
}
|
評分
-
查看全部評分
|