竹園論壇

標題: b017 - B.家長會問題 [打印本頁]

作者: ForTest 時間: 2014-4-28 07:51
標題: b017 - B.家長會問題
題目：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;
}

作者: Sylveon 時間: 2014-4-28 13:04
因為第二筆測資消失了

歡迎光臨竹園論壇 (http://forum.tfcis.org/)