大家好，我是小码匠。
今天回到家，最近刷的最爽的一道题，5分钟搞定。其实是有些水啊。。。
前置知识
- 图论
路漫漫其修远兮，吾将上下而求索
离自己的既定目标：
- 目标：300道
- 已完成：23道
- 待完成：277道
题目地址
- https://www.usaco.org/index.php?page=viewproblem2&cpid=940
牛奶生意正红红火火！Farmer John的牛奶加工厂内有N个加工站，编号为1…N（1≤N≤100），以及N−1条通道，每条连接某两个加工站。（通道建设很昂贵，所以Farmer John选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。
为了创新和提升效率，Farmer John在每条通道上安装了传送带。不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。
然而，Farmer John认为事情可能还不算完全失败，只要至少还存在一个加工站i满足从其他每个加工站出发都可以到达加工站i。注意从其他任意一个加工站j前往加工站i可能会经过i和j之间的一些中间站点。请帮助Farmer John求出是否存在这样的加工站i。
输入格式（文件名：factory.in）：
输入的第一行包含一个整数N，为加工站的数量。以下N−1行每行包含两个空格分隔的整数ai和bi，满足1≤ai,bi≤N以及ai≠bi。这表示有一条从加工站ai向加工站bi移动的传送带，仅允许沿从ai到bi的方向移动。
输出格式（文名：factory.out）：
如果存在加工站i满足可以从任意其他加工站出发都可以到达加工站i，输出最小的满足条件的i。否则，输出−1。
输出样例：
代码语言：javascript复制3
1 2
3 2
输出样例：
代码语言：javascript复制2
知识点
- floyd
题解
- 跑个floyd，比较水，第一次提交挂了2个测试点，把
-1的case给漏掉了。
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
bool g[105][105];
void best_coder() {
int n;
cin >> n;
memset(g, false, sizeof(g));
for (int i = 1; i < n; i) {
int u, v;
cin >> u >> v;
g[v][u] = true;
g[i][i] = true;
}
g[n][n] = true;
for (int i = 1; i <= n; i) {
for (int j = 1; j <= n; j) {
if (i == j) {
continue;
}
for (int k = 1; k <= n; k) {
if (i == j || i == k) {
continue;
}
g[j][k] = g[j][k] || (g[j][i] && g[i][k]);
}
}
}
for (int i = 1; i <= n; i){
bool is = true;
for (int j = 1; j <= n; j) {
if (!g[i][j]) {
is = false;
break;
}
}
if (is) {
cout << i;
return;
}
}
cout << -1;
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout.tie(nullptr);
freopen("factory.in", "r", stdin);
freopen("factory.out", "w", stdout);
// 小码匠
best_coder();
// 最优解
// happy_coder();
fclose(stdin);
fclose(stdout);
return 0;
}
学习代码
代码语言：javascript复制#include <bits/stdc .h> // see /general/running-code-locally
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair
void setIO(string name = "") {
cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
if (sz(name)) {
(void)!freopen((name ".in").c_str(), "r", stdin); // see /general/io
(void)!freopen((name ".out").c_str(), "w", stdout);
}
}
int in_deg[101], out_deg[101];
int main() {
setIO("factory");
int N;
cin >> N;
// N - 1 edges in a tree
for (int i = 0; i < N - 1; i ) {
// a -> b
// out[a] , in[b] ;
int a, b;
cin >> a >> b;
out_deg[a] ;
in_deg[b] ;
}
bool encountered_sink = false;
int idx_sink = -1;
for (int i = 1; i <= N; i ) {
if (encountered_sink && out_deg[i] == 0 && in_deg[i] > 0) {
idx_sink = -1; // answer
break;
}
if (out_deg[i] == 0 && in_deg[i] > 0) {
encountered_sink = true;
idx_sink = i;
}
}
cout << idx_sink << endl;
}
