統計得票最多的人,,投票具有傳遞性,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; }