首页 > 代码库 > HDU 3357

HDU 3357

2024-08-05 08:35:47   215人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=3357

给出公司间的控股关系，问有多少组不合法数据，自己控股自己不合法，a控股b，b控股c，则a控股c

其实就是找环，加一条边如果出现环ans++，但是每次搜一遍有没有环会tle。此处用邻接矩阵处理，如果a要控股b，则控股a的公司都控股b，并且a控股的公司都被控股a的控股。对于b的分析同理，此题有大量重复数据，需要去掉

#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <queue>#include <cmath>#include <stack>#include <set>using namespace std;int mp[300][300];int n;void add(int a,int b){    mp[a][b]=1;    for(int i=1;i<=n;i++)        if(mp[i][a]){            mp[i][b]=1;            for(int j=1;j<=n;j++)                if(mp[a][j])                    mp[i][j]=1;        }    for(int i=1;i<=n;i++)        if(mp[b][i]){            mp[a][i]=1;            for(int j=1;j<=n;j++)                if(mp[j][b])                    mp[j][i]=1;        }}int main(){    int t;    int cas=1;    while(~scanf("%d%d",&n,&t)){        if(!n && !t)break;        memset(mp,0,sizeof(mp));        int ans=0;        while(t--){            int a,b;            scanf("%d%d",&a,&b);                if(mp[b][a])ans++;            else if(a==b)ans++;            else if(!mp[a][b]) add(a,b);//关键，去除重复边，直接else会TLE         }        printf("%d. %d\n",cas++,ans);    }    return 0;}
View Code

 

HDU 3357


联系
我们