2016ACMICPC亚洲区大连站重现赛1001 Wrestling Match

待我称王封你为后i 2022-07-15 09:11 168阅读 0赞

**[菜鸟写题，多多指教 ][Link 1]**

**[HDU 5971Wrestling Match][]**

题意 ：n(<=1000)个人，其中有个x好人，y个坏人m(<=10000)场比赛，胜者为好人，负者为坏人

问能通过这些比赛是否可能将所有人分为好人或坏人。也就是每个人都有一状态，并且和比赛不冲突；

//输入

n m x y

5  4 1 0

//对手，也就是关系

a b

1 3

1 4

3 5

4 5

//x个好人的列表

//y个坏人的列表

//输出

YES

遍历所有相关集，所有集合都满足 (状态不冲突，所有人有状态) 则输出YES；

遍历参数是相关集，每个集合最多两种情况，

确定一个人可以确定相关集里的所有人；

vector c\[1010\]存关系；

int a\[1010\] 存状态；

set <int>  s\[1010\]存集合

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int n,m,x,y;
        //freopen("in.txt","r",stdin);
        while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF)
        {
            vector<int> c[1010];//关系
            int ac[1010];//状态,ac[0]不存
            memset(ac,0,sizeof(ac));
            int k = 0;//集合数
            set<int> s[1010];
            for(int ii = 0; ii < m; ii++){
                int a,b;
                scanf("%d%d",&a,&b);
                c[a].push_back(b);
                c[b].push_back(a);
                int ka = 0,kb = 0;//a,b所在集合，没有为0；
                for(int i = 1; i <= k; i++){
                    if(s[i].find(a)!= s[i].end()) ka = i;
                    if(s[i].find(b)!= s[i].end()) kb = i;
                }
                if(!ka && !kb){     //a,b都没有所属集合
                    k++;
                    s[k].insert(a);
                    s[k].insert(b);
                }
                else if(!ka)  //a没有所属集合
                    s[kb].insert(a);
                else if(!kb)    //b没有
                    s[ka].insert(b);
                else if(ka != kb){  //a,b都有，合并两集合并s[ka]标记为无效
                    if(s[ka].size() > s[kb].size()) swap(ka,kb);
                    set<int>::iterator it;
                    for(it = s[ka].begin(); it != s[ka].end(); it++)
                        s[kb].insert(*it);
                    s[ka].clear();
                    s[ka].insert(-10);
                }
    
            }
            /*
            for(int i = 1; i <= k; i++)//print all sets
            {
                cout<<i<<":  ";
                for(set<int>::iterator it = s[i].begin(); it != s[i].end(); it++)
                {
                    cout<<*it<<" ";
                }
                cout<<endl;
            }
            */
            for(int i = 0; i < x; i++)
            {
                int a;
                scanf("%d",&a);
                ac[a] = 1;
            }
            for(int i = 0; i < y; i++)
            {
                int a;
                scanf("%d", &a);
                ac[a] = -1;
            }
            //cout<<k<<endl;
            int ok = 1;
            for(int i = 1; i <= k; i++)///visit sets;
            {
                set<int>::iterator it = s[i].begin();
                if(*it == -10) continue;
                for(it; it != s[i].end(); it++)
                {
                    if(ac[*it]) break;
                }
                if(it == s[i].end())//集合中没有已经确定的元素；假设一种状态
                {
                    it = s[i].begin();
                    ac[*it] = 1;
                    //cout<<*it<<"  "<<i<<"  "<< -ac[*it]<<"  **"<<endl;
                }
    
                int tip[1010]; //是否已经被访问不能仅从ac[] == 0来判断
                memset(tip,0,sizeof(tip));
                queue<int> q;
                q.push(*it);
                while(!q.empty())
                {
                    int q1 = q.front();
                    q.pop();
                    if(tip[q1]) continue;
                    else tip[q1] = 1;
                    for(int i = 0; i < c[q1].size(); i++)
                    {
                        if(!ac[c[q1][i]])//对手没有性质
                        {
                            ac[c[q1][i]] = -ac[q1];
                            q.push(c[q1][i]);
                        }
                        else if(ac[c[q1][i]] == ac[q1])
                        {
                            ok = 0;  //对手和自己性质相同
                            //cout<<q1<<" == "<<c[q1][i]<<endl;
                            break;
                        }
                        else
                        {
                            q.push(c[q1][i]);
                        }
                    }
                    if(!ok) break; //已经违反，不再进行循环
                }
            }
            for(int i = 1; i <= n; i++)
            {
                //cout<<ac[i]<<"   x"<<endl;
                if(!ac[i])
                {
                    ok = 0;
                    //break;
                }
            }
            if(ok) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;;
    
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/ecjtusanhu/article/details/53121390
[HDU 5971Wrestling Match]: http://acm.hdu.edu.cn/showproblem.php?pid=5971