556队内第一次组队练习赛在上周日进行，总体情况不容乐观。现将赛后练习总结如下，能力一般水平有限，目前暂时只能做几道水题。希望自己能够不断进步。
A.Wrestling Match 摔跤大赛(HDU5971)
题意：某地举行摔跤大赛，其中n个参赛选手，已知这n个选手中有x个选手是 Good Player，有y个选手是 Bad Player，比赛规定每场对局的双方必须有一个是 Good Player， 有一个是 Bad Player，现给出 m场比赛的双方对阵信息，并且知道 x个好选手和 y个坏选手分别是谁，问根据已知信息，能否将所有的参赛选手分为 Good Player和 Bad Player。
分析：这道题思路其实很好想到，我遇到的最大困难出现在代码实现上。细细思考，其实就是判断是否有冲突的对局，从而可以抽象出一张图，问题转化为对这张图进行涂色，每条边两个端点的颜色必须不同，问能否成功涂满的问题。通过题目数据可以得到如果一个人既没有比赛也没有在输入中给出他是 Good Player还是 Bad Player，整张图就不能成功涂色。我个人的算法是先判断这个特判，如果有一个人既没有临接点也没有被确定身份，那么flag直接为0， break。然后将所有至少拥有一个已知颜色的点的联通分量依次涂色，若出现冲突则break。最后确定没有已知颜色端点的联通分量的涂色情况，任选其中一点确定任意一种颜色涂色即可，（因为只有两种颜色所以不论初值赋哪种颜色的是一样的，只需要判断可行性），通过这三层考验的数据，输出YES，若其中一个失败了，则输出NO。
很水的一道题，却做了很长时间，归根结底还是代码能力太差，邻接表在acm中的应用要比邻接矩阵广，虽然现在我还没有明白开始为什么用邻接矩阵做会有错误（可能还是有些地方写的不对），但在以后的比赛中还是要多多去用邻接表这种数据结构。还有就是在写长段代码的时候还是要给自己加一些注释，毕竟自己的智力还是没有那么高，每一个变量该怎么命名还是要养成良好的习惯。
AC代码如下（用1代表 Good Player，2代表 Bad Player，0代表未确定，代码有部分缺失，正在解决中）：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#define ll long long #define endl "\n" #define DE cout << "------" << endl #define mems(a, b) memset(a, b, sizeof a) #define pii pair<int, int> using namespace std; const int maxn = 1111; struct node { int u, v, next; } edge[20005]; struct E { int w, id; }; queue q; int head[1005], cnt, vis[1005]; void addedge(int u, int v) { edge[cnt].u = u; edge[cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++; edge[cnt].u = v; edge[cnt].v = u; edge[cnt].next = head[v]; head[v] = cnt++; } int n,m,x,y; int main(){ ios::sync_with_stdio(false); while(cin>>n>>m>>x>>y){ memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); cnt=0; for(int i=1;i<=m;i++){ int a,b; cin>>a>>b; addedge(a,b); } for(int i=0;i<x;i++){ int a; cin>>a; vis[a]=1; } for(int i=0;i<y;i++){ int a; cin>>a; vis[a]=2; } int flag=1; for(int i=1;i<=n;i++){ if(head[i]==-1&&vis[i]==0){ flag=0; // cout<<"1"<<endl; break; } } if(flag==1){ queue q; while(!q.empty()){//对所有拥有已确定点的联通分枝进行染色 q.pop(); } for(int i=1;i<=n;i++){ if(vis[i]!=0){ q.push(i); } } while(!q.empty()){ int xy=q.front(); q.pop(); for(int i=head[xy];i!=-1;i=edge[i].next){ int yy=edge[i].v; if(vis[yy]==0){ vis[yy]=3-vis[xy]; edge[i].u=yy; q.push(yy); } else if(vis[xy]==vis[yy]){ flag=0; // cout<<"2"<<endl; break; } } } for(int i=1;i<=n;i++){//对所有尚未染色的联通分枝进行染色 if(vis[i]==0){ queue q1; while(!q1.empty()){ q1.pop(); } vis[i]=1; q1.push(i); while(!q1.empty()){ int xx=q1.front(); q1.pop(); for(int j=head[xx];j!=-1;j=edge[j].next){ int yyy=edge[j].v; if(vis[yyy]==0){ vis[yyy]=3-vis[xx]; edge[j].u=yyy; q1.push(yyy); } else if(vis[yyy]==vis[xx]){ flag=0; break; } } } } } } if(flag){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } } |