首页 > 代码库 > la3211
la3211
2-sat+二分。。。
每次二分答案然后连边2-sat。。。边要开到n*n
样例水得跟没有一样。。。
#include<bits/stdc++.h> using namespace std; const int N = 4010; struct edge { int nxt, to; } e[N * N << 1]; int n, cnt = 1, top, Time, cot; int dfn[N], low[N], vis[N], st[N], early[N], late[N], head[N], belong[N]; void link(int u, int v) { e[++cnt].nxt = head[u]; head[u] = cnt; e[cnt].to = v; } void tarjan(int u) { st[++top] = u; dfn[u] = low[u] = ++Time; vis[u] = 1; for(int i = head[u]; i; i = e[i].nxt) { if(!dfn[e[i].to]) { tarjan(e[i].to); low[u] = min(low[u], low[e[i].to]); } else if(vis[e[i].to]) low[u] = min(low[u], dfn[e[i].to]); } if(dfn[u] == low[u]) { ++cot; int x = 0; while(x != u) { x = st[top--]; belong[x] = cot; vis[x] = 0; } } } bool judge(int t) { memset(head, 0, sizeof(head)); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(belong, 0, sizeof(belong)); cnt = 1; top = Time = cot = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(i != j) { int x = i << 1, y = j << 1; if(late[i] - late[j] >= 0 && late[i] - late[j] < t) link(x, y - 1), link(y, x - 1); if(late[i] - early[j] >= 0 && late[i] - early[j] < t) link(x, y), link(y - 1, x - 1); if(early[i] - late[j] >= 0 && early[i] - late[j] < t) link(x - 1, y - 1), link(y, x); if(early[i] - early[j] >= 0 && early[i] - early[j] < t) link(x - 1, y), link(y - 1, x); } for(int i = 1; i <= 2 * n; ++i) if(!dfn[i]) tarjan(i); for(int i = 1; i <= n; ++i) if(belong[i * 2] == belong[i * 2 - 1]) return false; return true; } int main() { while(scanf("%d", &n) != EOF) { int l = 0, r = 0, ans = 0; for(int i = 1; i <= n; ++i) scanf("%d%d", &early[i], &late[i]), r = max(r, late[i]); while(r - l > 1) { int mid = (l + r) >> 1; if(judge(mid)) ans = l = mid; else r = mid; } printf("%d\n", ans); } return 0; }
la3211
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。