【第023题】题解代码分享：这题真的很水吗？USACO 2019 Milk Factory

小码匠

发布于 2023-12-13 10:57:00

1430

发布于 2023-12-13 10:57:00

文章被收录于专栏：小码匠和老码农小码匠和老码农

大家好，我是小码匠。

今天回到家，最近刷的最爽的一道题，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。

输出样例：

3
1 2
3 2

输出样例：

知识点

floyd

题解

跑个floyd，比较水，第一次提交挂了2个测试点，把-1的case给漏掉了。

AC代码

#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;
}

学习代码

#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;
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2023-12-07，如有侵权请联系 cloudcommunity@tencent.com 删除

cin