CSU 1580Outing 強連通+背包
來源：程序員人生 發布時間：2015-07-27 07:54:54 閱讀次數：3979次
題目鏈接：點擊打開鏈接
給定n個人，車的載人量m
下面給出a[i]數組
想要約請i上車，必須先約請a[i]上車
問：最多能約請到多少人。
視察得到，這是1個有向圖，依照i->a[i]建邊后得到的圖是類似于樹形，但鏈的尾部是1個簡單環。
以下：
5 2
2 3 4 1 4
則我們必須先同時約請1234，才能約請5.
所以建立1個反圖（即邊的方向相反），然后強連通縮點1下，這樣就得到了1個森林（多個樹的圖）。
且對1個樹，只有根節點是需要同時約請的（由于根節點是個環，子節點都是單個點），而子節點是可以單個約請，約請任意數量的。
所以實際上對1個樹我們只需要關心這個樹的根節點本身的點數siz[root] 和 根節點子樹的點數son[root]（不包括根節點本身）
dfs1下處理出siz 和 son
然后利用這兩個進行背包
必須先用siz背包，得到的基礎上用son背包。
#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, 0, 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, 0, 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, 0, 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, 0, 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
*/
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
