日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > php開源 > php教程 > HDU 3639 Hawk-and-Chicken (強連通分量+樹形DP)

HDU 3639 Hawk-and-Chicken (強連通分量+樹形DP)

來源:程序員人生   發布時間:2015-03-20 08:58:02 閱讀次數:2430次

題目地址:HDU 3639

先用強連通份量縮點,縮點以后,再重新按縮點以后的塊逆序構圖,每一個塊的值是里邊縮的點的個數,那末得到選票的最大的1定是重新構圖后入度為0的塊,然后求出來找最大值便可。

代碼以下:

#include <iostream> #include <string.h> #include <math.h> #include <queue> #include <algorithm> #include <stdlib.h> #include <map> #include <set> #include <stdio.h> using namespace std; #define LL long long #define pi acos(⑴.0) const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e⑼; const int MAXN=5000+10; const int MAXM=30000+10; int head[MAXN], cnt, low[MAXN], dfn[MAXN], belong[MAXN], instack[MAXN], stk[MAXN], dp[MAXN]; int ans, indx, top; struct node { int u, v, next; }edge[MAXM]; void add(int u, int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void tarjan(int u) { low[u]=dfn[u]=++indx; instack[u]=1; stk[++top]=u; for(int i=head[u];i!=⑴;i=edge[i].next){ int v=edge[i].v; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ ans++; while(1){ int v=stk[top--]; belong[v]=ans; dp[ans]++; instack[v]=0; if(u==v) break; } } } void init() { memset(head,⑴,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(instack,0,sizeof(instack)); memset(dp,0,sizeof(dp)); cnt=ans=indx=top=0; } int head1[MAXN], cnt1, vis[MAXN], in[MAXN], max1, sum; struct node1 { int u, v, next; }edge1[MAXM]; void add1(int u, int v) { edge1[cnt1].v=v; edge1[cnt1].next=head1[u]; head1[u]=cnt1++; } void dfs(int u) { vis[u]=1; sum+=dp[u]; for(int i=head1[u];i!=⑴;i=edge1[i].next){ int v=edge1[i].v; if(!vis[v]){ dfs(v); } } } void init1() { memset(head1,⑴,sizeof(head1)); memset(vis,0,sizeof(vis)); memset(in,0,sizeof(in)); cnt1=0; max1=0; } int c[MAXN], tot, d[MAXN]; int main() { int t, n, m, i, j, u, v, Case=0; scanf("%d",&t); while(t--){ Case++; scanf("%d%d",&n,&m); init(); while(m--){ scanf("%d%d",&u,&v); add(u,v); } for(i=0;i<n;i++){ if(!dfn[i]) tarjan(i); } init1(); for(i=0;i<n;i++){ for(j=head[i];j!=⑴;j=edge[j].next){ if(belong[i]!=belong[edge[j].v]){ add1(belong[edge[j].v],belong[i]); in[belong[i]]++; } } } memset(d,⑴,sizeof(d)); for(i=1;i<=ans;i++){ if(!in[i]){ sum=0; memset(vis,0,sizeof(vis)); dfs(i); d[i]=sum; max1=max(max1,d[i]); } } tot=0; for(i=0;i<n;i++){ if(d[belong[i]]==max1) c[tot++]=i; } printf("Case %d: %d ",Case, max1⑴); for(i=0;i<tot;i++){ printf("%d",c[i]); if(i!=tot⑴) printf(" "); } puts(""); } return 0; }


生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 成人久久久 | sese国产| 亚洲午夜在线观看 | 久久久久久久国产精品影院 | 亚洲欧美久久 | 免费一看一级毛片 | 在线播放日韩 | 亚洲免费在线观看视频 | 欧美色综合一区二区三区 | 秋霞在线观看视频 | 91免费观看视频 | h片在线观看视频免费免费 日韩国产一区二区 | 成人精品视频99在线观看免费 | 欧美精品在线一区 | 99成人在线视频 | 可以在线观看的av网站 | 亚洲夜夜夜| 嫩草影院在线观看视频 | 一区色| 亚洲日韩欧美一区二区在线 | 久久国产精品视频 | 国产精品一区二区久久 | 三级视频在线播放 | 中文字幕一区二区三区四区在线观看 | 国内免费精品视频 | 国产午夜精品一区二区三区嫩草 | 久久69精品久久久久久久电影好 | 日韩成人免费在线 | 性色av一区二区三区 | 日韩一区二区视频 | 日韩精品免费在线视频 | 国产精品久久久久久久久免费 | 一区精品视频 | 欧美视频一区 | 欧美日韩国产色 | 国产美女被遭强高潮免费网站 | 国产婷婷色一区二区三区 | 亚洲аv电影天堂网 | 自拍视频第一页 | 久热免费视频 | 国产精品久久久久一区二区三区 |