【Codeforces 782D】Innokenty and a Football League

相关链接

题目传送门:http://codeforces.com/contest/782/problem/D

吐槽

为什么题面这么难懂啊?!
感觉出题人的英文比我好不到哪里去啊?!
差一点写成二分图了,还好室友嘈代码难写的时候多问了一句 _(:з」∠)_

解题报告

我们发现每个人只有两个状态
于是我们撸一发2-SAT就可以A辣!

Code

2-SAT判定有没有解是可以做到$O(m)$的,写个强连通就可以了
不过我这份代码是$O(m^2)$的啊!
为什么不会T?我的$m$是$O(n^2)$的啊

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000;
const int M = 5000009;

int n,que[N],cnt,head[N],to[M],nxt[M],mark[N];
char pat[2][100];
struct Data{
	char p[4];
	inline bool operator < (const Data &B) const {
		for (int i=0;i<3;i++) {
			if (p[i] < B.p[i]) return 1;
			else if (p[i] > B.p[i]) return 0;
		} return 0;
	}
	inline bool operator == (const Data &B) const {
		return !(*this < B) && !(B < *this);
	}
}c1[N],c2[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
}

inline int id(int w, int t) {
	return (w-1)*2 + t + 1;
}

bool DFS(int w) {
    if (mark[w]) return true;
    if (mark[w^1]) return false;
    mark[w] = 1; que[++cnt] = w;
     
    for (int i=head[w];i;i=nxt[i]) 
        if (!DFS(to[i])) return false;
    return true;
}
 
inline bool judge(){
    for (int i=2,lim=id(n,2);i<=lim;i+=2) if (!mark[i] && !mark[i+1]) {
        cnt = 0; if (DFS(i)) continue;
        for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
        cnt = 0; if (!DFS(i+1)) return false; 
    }
    return true;
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) {
		scanf("%s%s",pat[0],pat[1]);
		Data a; a.p[3] = 0; a.p[0] = pat[0][0]; a.p[1] = pat[0][1]; a.p[2] = pat[0][2];
		Data b; b.p[3] = 0; b.p[0] = pat[0][0]; b.p[1] = pat[0][1]; b.p[2] = pat[1][0];
		c1[i] = a; c2[i] = b;
	}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			if (i == j) continue; 
			if (c1[i] == c1[j]) Add_Edge(id(i, 2), id(j, 2));
			if (c1[i] == c1[j]) Add_Edge(id(i, 1), id(j, 2));
			if (c1[i] == c2[j]) Add_Edge(id(i, 1), id(j, 1));
			if (c2[i] == c1[j]) Add_Edge(id(i, 2), id(j, 2));
			if (c2[i] == c2[j]) Add_Edge(id(i, 2), id(j, 1));
		}
	}
	if (!judge()) puts("NO");
	else {
		puts("YES");
		for (int i=1;i<=n;i++) {
			if (mark[id(i, 1)]) printf("%s\n",c1[i].p);
			else printf("%s\n",c2[i].p);
		}
	} 
	return 0;
}

—————————— UPD 2017.3.27 ——————————
今天才知道输出一组可行解也是可以$O(m)$的
大概就是搞一发Tarjan,然后在拓扑图上按拓扑逆序染色

3 thoughts to “【Codeforces 782D】Innokenty and a Football League”

  1. 找了半天只有你一篇博文是用2-sat做的….但是我的2-sat写了好久,都没过,所以想问你几个问题。
    第一个是你加边的时候,id(i,2),id(j,2),意思是不是就是两个字符串的第一种选择是相同的,就把他们的第二种选择连一条边?
    第二个就是你是怎么限制当任意一个字符串选择第二种的时候,其他字符串不能和这个字符串的第一个一样?就是这句话” Apart from this, there is a rule that if for some club x the second option of short name is chosen, then there should be no club, for which the first option is chosen which is the same as the first option for the club x. ”

    如果可以的话,希望可以回答一下,谢谢….

  2. Sweet blog! I found it while surfing around on Yahoo News. Do you have any suggestions on how to get listed in Yahoo News? I’ve been trying for a while but I never seem to get there! Cheers

Leave a Reply

Your email address will not be published. Required fields are marked *