首页 > 代码库 > 【USACO 2.3】Controlling Companies （递推）
【USACO 2.3】Controlling Companies （递推）
题意：A公司对B公司有控制权的条件是满足下面条件之一：A=B，A对B的股份超过50%，A控制的公司对B的股份之和超过50%。
分析：我把控制关系分个等级：第一级是直接的股份超过50%，第二级是至少需要隔着第一级控制的公司才能控制此公司，...
从第一级推到第二级，第二级推到第三级...结束条件是这一次没有增加任何控制关系。
http://train.usaco.org/usacoprob2?a=O1HFwuT0pRX&S=concom
/*TASK:concomLANG:C++*/#include<cstdio>#include<cstring>#include<algorithm>#define ll long long#define file(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout)using namespace std;#define N 105int m;int c[N][N],g[N][N];int main(){ file(concom); scanf("%d",&m); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d %d %d",&u,&v,&w); g[u][v]=w; if(w>50){ c[u][v]=1; } c[u][u]= c[v][v]=1; } for(int k=0;k==0;){ k=1; for(int i=1;i<=100;i++){ int ct=0,ut=0,con[N],ucn[N]; for(int j=1;j<=100;j++) if(c[i][j]){con[++ct]=j;} else{ ucn[++ut]=j;} for(int j=1;j<=ut;j++){ int sum=0; for(int l=1;l<=ct;l++) { sum+=g[con[l]][ucn[j]]; if(sum>50){ k=0; c[i][ucn[j]]=1; break; } } } } } for(int i=1;i<=100;i++) for(int j=1;j<=100;j++) if(i!=j&&c[i][j])printf("%d %d\n",i,j); return 0;}
【USACO 2.3】Controlling Companies （递推）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。