HDU 1814 Peaceful Commission / HIT 1917 Peaceful Commission /CJOJ 1288 和平委員會(2-sat模板題)

Description

The Public Peace Commission should be legislated in Parliament of The Democratic Republic of Byteland according to The Very Important Law. Unfortunately one of the obstacles is the fact that some deputies do not get on with some others.

The Commission has to fulfill the following conditions:
1.Each party has exactly one representative in the Commission,
2.If two deputies do not like each other, they cannot both belong to the Commission.

Each party has exactly two deputies in the Parliament. All of them are numbered from 1 to 2n. Deputies with numbers 2i-1 and 2i belong to the i-th party .

Task
Write a program, which:
1.reads the number of parties and the pairs of deputies that are not on friendly terms,
2.decides whether it is possible to establish the Commission, and if so, proposes the list of members,
3.writes the result

Input

In the first line there are two non-negative integers n and m. They denote respectively: the number of parties, 1 <= n <= 8000, and the number of pairs of deputies, who do not like each other, 0 <= m <=2 0000. In each of the following m lines there is written one pair of integers a and b, 1 <= a < b <= 2n, separated by a single space. It means that the deputies a and b do not like each other.
There are multiple test cases.

Output

The text should contain one word NIE (means NO in Polish), if the setting up of the Commission is impossible. In case when setting up of the Commission is possible the file should contain n integers from the interval from 1 to 2n, written in the ascending order, indicating numbers of deputies who can form the Commission. Each of these numbers should be written in a separate line. If the Commission can be formed in various ways, your program may write mininum number sequence.

Sample Input

3 2
1 3
2 4

Sample Output

1
4
5

Http

HDU:https://vjudge.net/problem/HDU-1814
HIT:https://vjudge.net/problem/HIT-1917
CJOJ:http://oj.changjun.com.cn/problem/detail/pid/1288

Source

2-sat

翻譯(By CJOJ)

根據憲法，Byteland民主共和國的公眾和平委員會應該在國會中通過立法程序來創立。 不幸的是，由于某些黨派代表之間的不和睦而使得這件事存在障礙。
此委員會必須滿足下列條件：
每個黨派都在委員會中恰有1個代表，
如果2個代表彼此厭惡，則他們不能都屬于委員會。
每個黨在議會中有2個代表。代表從1編號到2n。 編號為2i-1和2i的代表屬于第I個黨派。
任務
寫一程序：
輸入黨派的數量和關系不友好的代表對，
計算決定建立和平委員會是否可能，若行，則列出委員會的成員表。

題目大意

有n個組，每組里有兩個元素，現在給出m對元素不能都選擇的條件，求一個集合使得每組里面恰好選擇了一個元素且滿足上述m對條件

解決思路

這是一道2-sat的模板題。

我們設i和i'表示一個黨派中的兩個人，那么如果i與j不能夠共存，則說明若選i則必須選j'，同理，若選j則必須選擇j'。由此，我們可以建邊連圖。對于互相厭惡的兩個代表i,j連邊i->j'和j->i'。注意這是有向邊！

為什么是有向邊呢？

因為i與j互相厭惡不代表i'與j'互相厭惡，如果連了邊j'->i，那么意思是選j'必須選i（同時也表示一定不能選i'），但j'與i并不一定互相厭惡，所以連的邊一定是有向邊。

然后就是判斷的方法。因為題目要求要按字典序輸出，所以對于每一組，我們先檢查標號較小的那個(i)，如果不行，再檢查編號大的(i+1)

另外一點需要注意的是，由于要求字典序輸出，所以不能使用Tarjan縮點+拓撲排序的方法，只能用dfs一個一個判斷

代碼

//暴力染色法 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<vector> using namespace std;#define Other(x) ((x%2==0) ? (x-1) : (x+1) ) //Other(x) 表示與x同黨派的另一個人。這里用i和i+1來表示同黨派的兩個人(i為奇數)const int maxN=16050; const int inf=2147483647;int n,m; int cnt; vector<int> E[maxN];//用來存放邊 int color[maxN];//存染色時每個點的顏色,0代表還沒有填，1和2分別代表兩種顏色 int Ans[maxN];//臨時存放答案bool solve();//循環染色 bool dfs(int x);//檢查是否滿足沒有矛盾int main() {while (cin>>n>>m){n=n*2;int a,b;for (int i=1;i<=n;i++)E[i].clear();//因為HDU上是多組數據，所以每一次都要重新清空for (int i=1;i<=m;i++){cin>>a>>b;E[a].push_back(Other(b));E[b].push_back(Other(a));}if (solve()){for (int i=1;i<=n;i++)//輸出所有被染成1色的點if (color[i]==1)cout<<i<<endl;}elsecout<<"NIE"<<endl;} }bool solve() {memset(color,0,sizeof(color));for (int i=1;i<=n;i++){if (color[i]!=0)//如果這個點已經被染色（即前面已經給其染過色）continue;cnt=0;//臨時保存答案的計數器if (!dfs(i))//先嘗試把i染成1，若不行則在下面選擇Other(i){for (int j=1;j<=cnt;j++)//若要選擇Other(i)則要把之前檢查i是否滿足時用到的數組清空{color[Ans[j]]=0;color[Other(Ans[j])]=0;}cnt=0;//感謝dsl大佬的查錯，這里要加cnt=0,雖然說不加程序并不會出錯，但是會浪費一堆空間，若數據大時可能會出問題if (!dfs(Other(i)))//如果把Other(i)也染成1也不滿足，說明無解return 0;}}return 1; }bool dfs(int x) {if (color[x]==1)//如果該點已被染成1，說明滿足并返回return 1;if (color[x]==2)//如果該點已被染成2，說明矛盾return 0;color[x]=1;//把這一點染成1color[Other(x)]=2;//把其相對的點染成2cnt++;Ans[cnt]=x;//把這一點放入Ans中，方便后面清空for (int i=0;i<E[x].size();i++)//傳遞染色if (!dfs(E[x][i]))//如果傳遞失敗，說明矛盾return 0;return 1; }

轉載于:https://www.cnblogs.com/SYCstudio/p/7134050.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的HDU 1814 Peaceful Commission / HIT 1917 Peaceful Commission /CJOJ 1288 和平委员会(2-sat模板题)...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。