首先,根据题目,只有A对B的控制超过50%,A才有可能通过B公司控制其他公司,所以我们就可以对dfs进行极大的剪枝
如果A控制B公司,那就对所有的公司,对A加上B控制的股份,
code
/* ID:yueqi LANG:C++ TASK:concom */ #include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits.h> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define Si set<int> #define LL long long #define pb push_back #define PS printf(" ") #define Vi vector<int> #define LN printf("\n") #define lson l,m,rt << 1 #define rson m+1,r,rt<<1|1 #define SD(a) scanf("%d",&a) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define FF(i,a) for(int i(0);i<(a);i++) #define FD(i,a) for(int i(a);i>=(1);i--) #define FOR(i,a,b) for(int i(a);i<=(b);i++) #define FOD(i,a,b) for(int i(a);i>=(b);i--) #define readf freopen("concom.in","r",stdin) #define writef freopen("concom.out","w",stdout) const int maxn = 101; const long long BigP=999983; const long long INF = 0x5fffffff; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; const double pi = acos(-1.0); const double eps= 1e-7; using namespace std; int N,a[maxn][maxn]; int ans[maxn][maxn],top; int dfs(int i,int j){ FOR(k,1,top){ if(i!=k && ans[i][k]<50){ ans[i][k]+=a[j][k]; if(ans[i][k]>=50) dfs(i,k); } } } int main() { readf; writef; int p,q,c; SD(N); FOR(i,1,N){ SD(p);SD(q);SD(c); a[p][q]=c; ans[p][q]=c; if(p>top) top=p; if(q>top) top=q; } FOR(i,1,top) FOR(j,1,top){ if(ans[i][j]>=50) dfs(i,j); } FOR(i,1,top) FOR(j,1,top){ if(i!=j && ans[i][j]>=50){ PD(i);PS;PD(j);LN; } } return 0; }