首页 > 代码库 > hihocoder #1468 : 2-SAT·hihoCoder新春晚会 2-SAT

hihocoder #1468 : 2-SAT·hihoCoder新春晚会 2-SAT

2024-10-02 12:06:38   218人阅读

题目链接：

http://hihocoder.com/problemset/problem/1468

题意：

hihoCoder新春晚会正在紧张地筹备中。晚会分为上半场和下半场，总导演小Hi现在要为N个节目安排演出时间(上半场或下半场)。为了描述方便，我们将第i个节目对应两个编号2i－1和2i，分别表示把第i个节目安排在上半场和下半场。

由于演员、道具和布景的限制。有些安排之间存在冲突，比如编号1的安排和编号4的安排有冲突，意味着"把第1个节目安排在上半场"同"把第2个节目安排在下半场"有冲突。

现在小Hi手里有M对编号，表示冲突的节目安排。他的任务是帮助主办方安排出节目演出的合理时间。

输入

第一行包含两个非负整数n和m（n≤8000，m≤20000），代表有n个节目和m对冲突。

接下来m行每行两个数x和y，表示编号x和编号y冲突。

输出

输出n行，每行一个数，从小到大输出最后进行演出的编号。若有多解，则输出字典序最小的。无解则输出NIE。

样例输入

3 2
1 3
2 4

样例输出

1
4
5

思路：

u和v不能同时出现，所以对应的边就是 u->(v的另一个)，v->(u的另一个) 这两条，我们tarjan求出强联通分量，判断是否矛盾，如果r[i*2]==r[i*2-1]那么就矛盾，否则一定有解，因为要求字典序最小，所以我们编号从小的开始便利，如果这个节目上半场和下半场都没访问过，那么从上半场bfs[字典序的限制]，得到一条符合规则的链，如果出现矛盾，也就是也访问过这条链上某个点对应的相反的点，那么就从当前节目的下半场bfs过去。 说的很迷，，看代码把 

代码：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define MS(a) memset(a,0,sizeof(a))
  5 #define MP make_pair
  6 #define PB push_back
  7 const int INF = 0x3f3f3f3f;
  8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  9 inline ll read(){
 10     ll x=0,f=1;char ch=getchar();
 11     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
 12     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
 13     return x*f;
 14 }
 15 //////////////////////////////////////////////////////////////////////////
 16 const int maxn = 1e5+10;
 17 
 18 vector<int> g[maxn];
 19 
 20 void add(int u,int v){
 21     g[u].push_back(v);
 22 }
 23 
 24 int low[maxn],dfn[maxn],vis[maxn],ins[maxn],r[maxn],tot;
 25 stack<int> s;
 26 void tarjan(int u){
 27     low[u]=dfn[u] = ++tot;
 28     vis[u]=ins[u] = 1;
 29     s.push(u);
 30     for(int i=0; i<(int)g[u].size(); i++){
 31         int v = g[u][i];
 32         if(!vis[v]){
 33             tarjan(v);
 34             low[u] = min(low[u],low[v]);
 35         }else if(ins[v]){
 36             low[u] = min(low[u],dfn[v]);
 37         }
 38     }
 39 
 40     if(dfn[u] == low[u]){
 41         int t;
 42         do{
 43             t = s.top(); s.pop();
 44             r[t] = u;
 45             ins[t] = 0;
 46         }while(t != u);
 47     }
 48 }
 49 
 50 int tmp[maxn],ans[maxn];
 51 
 52 void bfs(int u){
 53     queue<int> q;
 54     q.push(u); vis[u] = 1;
 55     tmp[0] = 0;
 56     while(!q.empty()){
 57         int now = q.front(); q.pop();
 58         tmp[++tmp[0]] = now;
 59         for(int i=0; i<(int)g[now].size(); i++){
 60             int v = g[now][i];
 61             if(vis[v]) continue;
 62             vis[v] = 1;
 63             q.push(v);
 64         }
 65     }
 66 }
 67 
 68 bool judge(){
 69     for(int i=1; i<=tmp[0]; i++){
 70         if(vis[tmp[i]+(tmp[i]&1 ? 1 : -1)]) return false;
 71     }
 72     return true;
 73 }
 74 
 75 int main(){
 76     int n,m;
 77     cin >> n >> m;
 78     for(int i=0; i<m; i++){
 79         int u,v; scanf("%d%d",&u,&v);
 80         add(u,v+((v&1)?1:-1));
 81         add(v,u+((u&1)?1:-1));
 82     }
 83     for(int i=1; i<=2*n; i++){
 84         if(!dfn[i]) tarjan(i);
 85     }
 86 
 87     for(int i=1; i<2*n; i+=2){
 88         if(r[i] == r[i+1]){
 89             puts("NIE");
 90             return 0;
 91         }
 92     }
 93 
 94     MS(vis);
 95     for(int i=1; i<=n; i++){
 96         if(!vis[i*2] && !vis[i*2-1]){
 97             bfs(i*2-1);
 98             if(!judge()){
 99                 for(int j=1; j<=tmp[0]; j++) vis[tmp[j]] = 0;
100                 bfs(i*2);
101             }
102             for(int j=1; j<=tmp[0]; j++) ans[++ans[0]] = tmp[j];
103         }
104     }
105     sort(ans+1,ans+ans[0]+1);
106     for(int i=1; i<=n; i++){
107         cout << ans[i] << endl;
108     }
109 
110     return 0;
111 }

 

hihocoder #1468 : 2-SAT·hihoCoder新春晚会 2-SAT


联系
我们