CSU 1580Outing 强连通+背包
来源：程序员人生 发布时间：2015-07-27 07:54:54 阅读次数：3836次
题目链接：点击打开链接
给定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
*/
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
