CSU 1580Outing 强连通+背包

5 2 2 3 4 1 4

#include<iostream> #include<stdio.h> #include<string.h> #include<queue> #include<math.h> #include<set> #include<vector> using namespace std; template <class T> inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?⑴:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } const int N = 1005; //N为最大点数 const int M = 3000; //M为最大边数 int n,m;//n m 为点数和边数 struct Edge{ int from,to,nex; bool sign;//是不是为桥 }edge[M<<1]; int head[N],edgenum; void add(int u,int v){//边的出发点和终点 Edge E={u,v,head[u],false}; edge[edgenum] = E; head[u] = edgenum++; } int DFN[N],Low[N],Stack[N],top,Time; //Low[u]是点集{u点及以u点为根的子树} 中(所有反向弧)能指向的(离根最近的先人v) 的DFN[v]值(即v点时间戳) int taj;//连通分支标号，从1开始 int Belong[N];//Belong[i] 表示i点属于的连通分支 bool Instack[N]; vector<int> bcc[N]; //标号从1开始 void tarjan(int u,int fa){ DFN[u] = Low[u] = ++ Time ; Stack[top ++ ] = u ; Instack[u] = 1 ; for (int i = head[u] ; ~i ; i = edge[i].nex ){ int v = edge[i].to ; if(DFN[v] == ⑴) { tarjan(v,u) ; Low[u] = min(Low[u],Low[v]) ; if(DFN[u] < Low[v]) { edge[i].sign = 1;//为割桥 } } else if(Instack[v]) Low[u] = min(Low[u],DFN[v]) ; } if(Low[u] == DFN[u]){ int now; taj ++ ; bcc[taj].clear(); do{ now = Stack[-- top] ; Instack[now] = 0 ; Belong [now] = taj ; bcc[taj].push_back(now); }while(now != u) ; } } void tarjan_init(int all){ memset(DFN,⑴,sizeof(DFN)); memset(Instack,sizeof(Instack)); top = Time = taj = 0; for(int i=1;i<=all;i++)if(DFN[i]==⑴ )tarjan(i,i); //注意开始点标！！！ } vector<int>G[N]; int du[N],siz[N],son[N]; void suodian(){ memset(du,sizeof(du)); for(int i = 1; i <= taj; i++)G[i].clear(); for(int i = 0; i < edgenum; i++){ int u = Belong[edge[i].from],v = Belong[edge[i].to]; if(u!=v)G[u].push_back(v),du[v]++; } memset(siz,sizeof siz); for(int i = 1; i <= n; i++)siz[Belong[i]]++;//统计新图中每一个点实际上包括了旧图中多少个点 } void init(){memset(head,sizeof(head)); edgenum=0;} void dfs(int u){ son[u] = 0; for(int i = 0; i < G[u].size(); i++){ int v = G[u][i]; dfs(v); son[u] += son[v] + siz[v]; } } int dp[N],tmp[N]; void bei(int x){ for(int j = 0; j + x <= m; j++) dp[j] = max(dp[j],dp[j+x]+x); } void work(int x){ dfs(x); // printf("(%d,%d) ",siz[x],son[x]); memset(tmp,sizeof tmp); for(int j = 0; j + siz[x] <= m; j++) tmp[j] = max(tmp[j],dp[j+siz[x]]+siz[x]); // for(int i = 0; i <= m; i++)cout<<tmp[i]<<" ";puts(""); for(int i = 1; i <= son[x]; i++) { for(int j = 0; j+1<=m; j++) if(tmp[j+1]!=⑴) tmp[j] = max(tmp[j],tmp[j+1]+1); } for(int i = 0; i <= m; i++)dp[i] = max(dp[i],tmp[i]); } int main(){ while(~scanf("%d %d",&n,&m)){ init(); for(int i = 1,x; i <= n; i++){ rd(x); add(x,i); } tarjan_init(n); suodian(); // for(int i = 1; i <= taj; i++)printf("%d ",siz[i]);puts(" --siz"); memset(dp,sizeof dp); for(int i = 1; i <= taj ; i++)if(du[i] == 0)work(i); cout<<dp[0]<<endl; } return 0; } /* 4 4 2 3 3 4 ans:4 4 2 2 3 4 1 ans:0 6 4 2 3 4 5 6 3 ans:2 12 3 2 3 4 5 6 7 3 9 10 11 12 8 12 11 2 3 4 5 6 7 3 9 10 11 12 8 */