題意：略（忙著準備文化課。。。明天期中考啊。。。。

思路：

正解就是染色，2-sat搞；

AC代碼（雖然是錯誤的。。。數據水（過踏馬的也行啊，起碼打臉他啊！）

4 3 1 0

1 2

2 3

3 4

4

這個就掛了；

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAX=1010; const double q=(1+sqrt(5.0))/2.0; const double eps=1e-100; int n,m; int v[MAX]; int a[MAX][MAX]; int main() {int t,i,j;int x,y;while(~scanf("%d%d%d%d",&n,&m,&x,&y)){int flag=0;int b,c;memset(a,0,sizeof(a));memset(v,-1,sizeof(v));for(i=0;i<m;i++){scanf("%d%d",&b,&c);a[b][c]=a[c][b]=1;}for(i=1;i<=x;i++){scanf("%d",&b);for(j=0;j<n;j++){if(a[b][j]){if(v[j]==1)flag=1;v[j]=0;}}v[b]=1;}for(i=1;i<=y;i++){scanf("%d",&b);for(j=0;j<n;j++){if(a[b][j]){if(v[j]==0)flag=1;v[j]=1;}}v[b]=0;}for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(a[i][j]){if(v[i]==-1&&v[j]==-1){v[i]=1;v[j]=0;}else if(v[i]!=-1&&v[j]!=-1){if(v[i]+v[j]!=1)flag=1;}else if(v[i]!=-1){v[j]=1-v[i];}elsev[i]=1-v[j];}}}for(i=1;i<=n;i++){ // printf("%d ",v[i]);if(v[i]==-1)flag=1;} // puts("");if(flag)printf("NO\n");elseprintf("YES\n");}return 0; }
貼份應該正確的（escape

#include<bits/stdc++.h> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=5*1e4+1000; #define eps 1e-4 int co[10005]; int vis[10005]; vector<int>g[10005]; int dfs(int u) {int sz=g[u].size();for(int i=0; i<sz; i++){int v=g[u][i];if(!co[v]){co[v]=!co[u];if(!dfs(v))return 0;}else if(co[u]==co[v]){return 0;}}return 1; } int main() {int n,m,x,y;while(cin>>n>>m>>x>>y){for(int i=0; i<10005; i++)g[i].clear();if(n==1){puts("NO");continue;}for(int i=0; i<m; i++){int xx,yy;scanf("%d%d",&xx,&yy);g[xx].push_back(yy);}memset(co,0,sizeof(co));for(int i=0; i<x; i++){int xx;scanf("%d",&xx);co[xx]=1; // int sz=g[xx].size(); // for(int i=0; i<sz; i++) // { // int v=g[xx][i]; // co[v]=!co[xx]; // }}for(int i=0; i<y; i++){int xx;scanf("%d",&xx);co[xx]=0; // int sz=g[xx].size(); // for(int i=0; i<sz; i++) // { // int v=g[xx][i]; // co[v]=!co[xx]; // }}if(x==0&&y==0)puts("NO");else{int flag=1;for(int i=1; i<=n; i++)if(!dfs(i))flag=0;if(flag)puts("YES");elseputs("NO");}}return 0; }

加強后的瞎搞（求hack

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAX=1010; const double q=(1+sqrt(5.0))/2.0; const double eps=1e-100; int n,m; int v[MAX]; int a[MAX][MAX]; int main() {int t,i,j,k;int x,y;while(~scanf("%d%d%d%d",&n,&m,&x,&y)){int flag=0;int b,c;memset(a,0,sizeof(a));memset(v,-1,sizeof(v));for(i=0; i<m; i++){scanf("%d%d",&b,&c);a[b][c]=a[c][b]=1;}for(i=1; i<=x; i++){scanf("%d",&b);for(j=0; j<n; j++){if(a[b][j]){if(v[j]==1)flag=1;v[j]=0;}}v[b]=1;}for(i=1; i<=y; i++){scanf("%d",&b);for(j=0; j<n; j++){if(a[b][j]){if(v[j]==0)flag=1;v[j]=1;}}v[b]=0;}for(k=0; k<2; k++){for(i=1; i<=n; i++){for(j=1; j<=n; j++){if(a[i][j]){if(v[i]==-1&&v[j]==-1&&k){v[i]=1;v[j]=0;}else if(v[i]!=-1&&v[j]!=-1){if(v[i]+v[j]!=1)flag=1;}else if(v[i]!=-1){v[j]=1-v[i];}else if(v[j]!=-1)v[i]=1-v[j];}}}}for(i=1; i<=n; i++){ // printf("%d ",v[i]);if(v[i]==-1)flag=1;} // puts("");if(flag)printf("NO\n");elseprintf("YES\n");}return 0; } /* 6 5 0 0 1 2 2 3 3 4 3 1 5 66 5 0 0 1 2 2 3 3 4 4 1 5 64 3 1 0 1 2 2 3 3 4 4*/

轉載于:https://www.cnblogs.com/keyboarder-zsq/p/6216749.html

總結

以上是生活随笔為你收集整理的HDU5971【瞎搞】的全部內容，希望文章能夠幫你解決所遇到的問題。

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