【dfs】BZOJ1703-[Usaco2007 Mar]Ranking the Cows 奶牛排名

【题目大意】

农夫约翰有N(1≤N≤1000)头奶牛，每一头奶牛都有一个确定的独一无二的正整数产奶率．约翰想要让这些奶牛按产奶率从高到低排序，约翰已经比较了M(1≤M≤10000)对奶牛的产奶率，但他发现，他还需要再做一张关于另外C对奶牛的产奶率比较，才能推断出所有奶牛的产奶率排序。请帮他确定C的最小值。

【思路】

对于M对关系，从产奶率高的往产奶率低的连一条有向边。对于每个节点i，它能抵达的节点的总数即是能比较得出的比它小的奶牛总数。

由于原本总共有N*(N-1)/2对关系，ans=N*(N-1)/2-Σ从该头奶牛能抵达的节点总数。

 #include<bits/stdc++.h>

 using namespace std;

 const int MAXN=+;

 int n,m,ans,tmp;

 int vis[MAXN];

 vector<int> E[MAXN];

 void dfs(int u,int T)

 {

     for (int i=;i<E[u].size();i++)

     {

         int v=E[u][i];

         if (vis[v]!=T)

         {

             tmp++;

             vis[v]=T;

             dfs(v,T);

         }

     }

 }

 void init()

 {

     scanf("%d%d",&n,&m);

     for (int i=;i<=m;i++)

     {

         int u,v;

         scanf("%d%d",&u,&v);

         E[u].push_back(v);

     }

 }

 void solve()

 {

     ans=;

     memset(vis,,sizeof(vis));

     for (int i=;i<=n;i++)

     {

         tmp=;

         dfs(i,i);

         ans+=tmp;

     }

     ans=(n-)*n/-ans;

     printf("%d\n",ans);

 }

 int main()

 {

     init();

     solve();

     return ;

 }

巴特西

【dfs】BZOJ1703-[Usaco2007 Mar]Ranking the Cows 奶牛排名

最新文章

热门文章