USACO： controlling companie

本文主要是介绍USACO： controlling companie，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

类似于floyd的算法，不过在做完一遍之后，会引起下一次的改变（最后一组数组就是这样的，在这儿wa了），所以可能会做很多遍。设置一个flag，当某一遍没有引起改变时结束。

/*
ID: 
LANG: C++
TASK: concom
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>#define IN "concom.in"
#define OUT "concom.out"
#define M 105using namespace std;int con[M][M];
int map[M][M];
bool visited[M][M];
int n;void solve()
{memset(visited, false, sizeof(visited));bool flag = true;while(flag) {flag = false;for(int i = 1; i <= 100; i++) {for(int j = 1; j <= 100; j++) {if(con[i][j] > 50 && !visited[i][j]) {visited[i][j] = true;for(int k = 1; k <= 100; k++) {if(map[j][k]) {flag = true;con[i][k] += map[j][k];}}}}}}
}int main()
{freopen(IN, "rb", stdin);freopen(OUT, "wb", stdout);while(scanf("%d", &n) != EOF) {memset(con, 0, sizeof(con));for(int i = 0; i < n; i++) {int x, y, stock;scanf("%d%d%d", &x, &y, &stock);map[x][y] = stock;con[x][y] = stock;}solve();for(int i = 1; i <= 100; i++)for(int j = 1; j <= 100; j++)if(i != j && con[i][j] > 50)printf("%d %d\n", i, j);}fclose(stdin);fclose(stdout);return 0;
}

这篇关于USACO： controlling companie的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---