程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3639

hdu 3639

編輯:C++入門知識

統計得票最多的人,,投票具有傳遞性,a->b->c,c就得到兩票,剛開始想要是建反圖的話直接搜索所有入度為0的點(最大的一定是入度為0的點)答案就出來了,代碼敲了一半,才想到一個問題:要是幾個人投票形成一個環的話就不好解決了,

如果i個人形成一個環的話,每人都是i-1票,環之間還可以有聯系,

明顯就是強連通縮點問題,將環縮成點,然後建反圖直接搜索,就ok了,

 



 #include<stdio.h>  
#include<stack>  
#include<string.h>  
#define N 5010   
using namespace std; 
int n,m; 
int dfs[N],low[N],belong[N],ins[N],inq[N],num[N],cont[N],vis[N]; 
struct edage 
{ 
    int ed; 
    struct edage *next; 
}*E[N],*e[N]; 
void addedage(int x,int y) 
{ 
    struct edage *p=new edage; 
    p->ed=y; 
    p->next=E[x]; 
    E[x]=p; 
} 
void Addedage(int x,int y) 
{ 
    struct edage *p=new edage; 
    p->ed=y; 
    p->next=e[x]; 
    e[x]=p; 
} 
stack<int>Q; 
int idx,ans; 
void Tarjan(int x) 
{ 
    int v; 
    dfs[x]=low[x]=idx++; 
    Q.push(x); 
    ins[x]=1; 
    for(edage *j=E[x];j;j=j->next) 
    { 
        if(dfs[j->ed]==-1) 
        { 
            Tarjan(j->ed); 
            low[x]=low[x]>low[j->ed]?low[j->ed]:low[x]; 
        } 
        else if(ins[j->ed]==1) 
            low[x]=low[x]>dfs[j->ed]?dfs[j->ed]:low[x]; 
    } 
    if(low[x]==dfs[x]) 
    { 
        while(1) 
        { 
            v=Q.top(); 
            Q.pop(); 
            ins[v]=0; 
            belong[v]=ans; 
            num[ans]++; 
            if(v==x)break; 
        } 
        ans++; 
    } 
} 
int DFS(int x) 
{ 
    vis[x]=1; 
    int sum=0; 
    for(edage *q=e[x];q;q=q->next) 
        if(vis[q->ed]==0) 
            sum+=(num[q->ed]+DFS(q->ed)); 
        return sum; 
} 
int main() 
{ 
    int i,j,x,op=1,t,y; 
    scanf("%d",&t); 
    while(t--) 
    { 
        memset(E,NULL,sizeof(E)); 
        memset(e,NULL,sizeof(e)); 
        memset(dfs,-1,sizeof(dfs)); 
        memset(ins,0,sizeof(ins)); 
        memset(inq,0,sizeof(inq)); 
        memset(num,0,sizeof(num)); 
        memset(cont,0,sizeof(cont)); 
        scanf("%d%d",&n,&m); 
        for(i=0;i<m;i++) 
        { 
            scanf("%d%d",&x,&y); 
            addedage(x,y); 
        } 
        idx=ans=0; 
        for(i=0;i<n;i++) 
        { 
            if(dfs[i]==-1) 
                Tarjan(i);//縮點  
        } 
        for(i=0;i<n;i++) 
        { 
            for(edage *q=E[i];q;q=q->next) 
            { 
                if(belong[i]!=belong[q->ed]) 
                { 
                    inq[belong[i]]++; 
                    Addedage(belong[q->ed],belong[i]);//建反圖  
                } 
            } 
        } 
        int max=-1; 
        for(i=0;i<ans;i++) 
        { 
            memset(vis,0,sizeof(vis)); 
            if(inq[i]==0) 
            { 
                cont[i]=num[i]-1+DFS(i); 
                if(max<cont[i]) 
                {max=cont[i];} 
            } 
        } 
        printf("Case %d: %d\n",op++,max); 
        for(i=0;i<n;i++) 
            if(cont[belong[i]]==max) 
                break; 
            printf("%d",i++); 
            for(;i<n;i++) 
                if(cont[belong[i]]==max) 
                    printf(" %d",i); 
                printf("\n"); 
    } 
    return 0; 
} 

#include<stdio.h>
#include<stack>
#include<string.h>
#define N 5010
using namespace std;
int n,m;
int dfs[N],low[N],belong[N],ins[N],inq[N],num[N],cont[N],vis[N];
struct edage
{
 int ed;
 struct edage *next;
}*E[N],*e[N];
void addedage(int x,int y)
{
 struct edage *p=new edage;
 p->ed=y;
 p->next=E[x];
 E[x]=p;
}
void Addedage(int x,int y)
{
 struct edage *p=new edage;
 p->ed=y;
 p->next=e[x];
 e[x]=p;
}
stack<int>Q;
int idx,ans;
void Tarjan(int x)
{
 int v;
 dfs[x]=low[x]=idx++;
 Q.push(x);
 ins[x]=1;
 for(edage *j=E[x];j;j=j->next)
 {
  if(dfs[j->ed]==-1)
  {
   Tarjan(j->ed);
   low[x]=low[x]>low[j->ed]?low[j->ed]:low[x];
  }
  else if(ins[j->ed]==1)
   low[x]=low[x]>dfs[j->ed]?dfs[j->ed]:low[x];
 }
 if(low[x]==dfs[x])
 {
  while(1)
  {
   v=Q.top();
   Q.pop();
   ins[v]=0;
   belong[v]=ans;
   num[ans]++;
   if(v==x)break;
  }
  ans++;
 }
}
int DFS(int x)
{
 vis[x]=1;
 int sum=0;
 for(edage *q=e[x];q;q=q->next)
  if(vis[q->ed]==0)
   sum+=(num[q->ed]+DFS(q->ed));
  return sum;
}
int main()
{
 int i,j,x,op=1,t,y;
 scanf("%d",&t);
 while(t--)
 {
  memset(E,NULL,sizeof(E));
  memset(e,NULL,sizeof(e));
  memset(dfs,-1,sizeof(dfs));
  memset(ins,0,sizeof(ins));
  memset(inq,0,sizeof(inq));
  memset(num,0,sizeof(num));
  memset(cont,0,sizeof(cont));
  scanf("%d%d",&n,&m);
  for(i=0;i<m;i++)
  {
   scanf("%d%d",&x,&y);
   addedage(x,y);
  }
  idx=ans=0;
  for(i=0;i<n;i++)
  {
   if(dfs[i]==-1)
    Tarjan(i);//縮點
  }
  for(i=0;i<n;i++)
  {
   for(edage *q=E[i];q;q=q->next)
   {
    if(belong[i]!=belong[q->ed])
    {
     inq[belong[i]]++;
     Addedage(belong[q->ed],belong[i]);//建反圖
    }
   }
  }
  int max=-1;
  for(i=0;i<ans;i++)
  {
   memset(vis,0,sizeof(vis));
   if(inq[i]==0)
   {
    cont[i]=num[i]-1+DFS(i);
    if(max<cont[i])
    {max=cont[i];}
   }
  }
  printf("Case %d: %d\n",op++,max);
  for(i=0;i<n;i++)
   if(cont[belong[i]]==max)
    break;
   printf("%d",i++);
   for(;i<n;i++)
    if(cont[belong[i]]==max)
     printf(" %d",i);
    printf("\n");
 }
 return 0;
}

 

 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved