abc139_E
abc139_E
题意简述:
\(n\) 个人进行 \(n(n -1)/2\) 场比赛,每个人都要以一个特定的顺序与其他人比赛,
且每个人每天只可以比一场比赛,问最少比赛的天数为多少,无解输出 \(-1\)
正解 :
发现一个人假如可以和另外一个打比赛时,和他打比赛肯定是最优的
因为另外那个人此时肯定也只可以和他打比赛,对除了这两人之外的其他人没有影响
每一场比赛都可以用一个二元组表示 \((x, y)\) 成一个节点,节点向节点连边表示限制
比如说第一个人要先后和第二个人和第三个人打比赛
那么 \((1, 2) \to (1,3)\)
这样的话只有入度为 \(0\) 的点(比赛)才可以进行,用 \(topo\) 排序做一下
有环的话肯定无解,没环的话答案就是最长链
前一个很好证明,关键是后面一个怎么证明
其实也挺好证,因为当前入度为 \(0\) 的节点(比赛)肯定都可以在同一天进行完
具体一点 :\((1,2) 和 (1,3)\) 肯定不会同时可以进行比赛(同时入度为 \(0\))
Code :
#include <algorithm> #include <iostream> #include <cstdio> #include <queue> #define N 1003 using namespace std; struct edge{ int to, nxt; }e[N * N * 3]; int n, cnt; int ins[N * N], mp[N][N], fir[N * N], t[N * N]; queue < int > Q; int id(int ,int); void add(int ,int); int main(){ scanf("%d", &n); int ans = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j < n; ++j) scanf("%d", mp[i] + j); for(int i = 1; i <= n; ++i) for(int j = 2; j < n; ++j) add(id(i, mp[i][j - 1]), id(i, mp[i][j])); for(int i = 1; i <= n * n; ++i){ if(!ins[i]) Q.push(i); t[i] = 1; } while(!Q.empty()){ int u = Q.front(); Q.pop(); ans = max(ans, t[u]); for(int i = fir[u]; i; i = e[i].nxt){ int v = e[i].to; --ins[v]; if(!ins[v]) Q.push(v), t[v] = t[u] + 1; } } for(int i = 1; i <= n * n; ++i) if(ins[i]) ans = -1; cout << ans << endl; return 0; } int id(int x,int y){ if(x > y) swap(x, y); return (x - 1) * n + y; } void add(int u,int v){ e[++cnt] = (edge){v, fir[u]}; fir[u] = cnt; ++ins[v]; return ; }
原文地址:https://www.cnblogs.com/Lskkkno1/p/11443826.html
相关推荐
-
由58同城爬虫浅谈量子力学人性的多重分身 c/c++
2019-10-7
-
面向对象设计与分析–概念篇 c/c++
2019-3-28
-
C语言指针专题——如何理解指针 c/c++
2019-3-30
-
C++中三种传递参数方法的效率分析 c/c++
2019-8-9
-
C、C++语言相关基础巩固 Round1 { 字节序、内存对齐 } c/c++
2020-6-15
-
现在市场上,C++ 主要用来做什么? c/c++
2019-10-16
-
数据结构-单向链表 c/c++
2019-6-29
-
C++:string_view 与 C API 的互操作性 c/c++
2019-5-18
-
linux 信号机制 c/c++
2019-3-30
-
大数运算之大数阶乘 c/c++
2019-8-9