首页 > 代码库 > Outing
Outing
Outing
题目描述
Organising a group trip for the elderly can be a daunting task... Not least because of the fussy participants, each of whom will only make the trip on condition that some other participant also comes.
After some effort, you have taken from each of your participants a number, indicating that this participant will refuse to join the excursion unless the participant with that number also joins– the less choosy simply give their own number. This would be easy enough to resolve (just send all of them) but the bus you are going to use during the trip has only a ?xed number of places.
Given the preferences of all participants, ?nd the maximum number of participants that can join.
After some effort, you have taken from each of your participants a number, indicating that this participant will refuse to join the excursion unless the participant with that number also joins– the less choosy simply give their own number. This would be easy enough to resolve (just send all of them) but the bus you are going to use during the trip has only a ?xed number of places.
Given the preferences of all participants, ?nd the maximum number of participants that can join.
输入
The ?rst line of input contains two integers n and k (1 ≤ k ≤ n ≤ 1 000), where n denotes the total number of participants and k denotes the number of places on the bus.
The second line contains n integers x i for i = 1, 2, . . . , n, where 1 ≤ x i ≤ n. The meaning of x i is that the i-th participant will refuse to join the excursion unless the x i -th participant also joins.
The second line contains n integers x i for i = 1, 2, . . . , n, where 1 ≤ x i ≤ n. The meaning of x i is that the i-th participant will refuse to join the excursion unless the x i -th participant also joins.
输出
Output one integer: the maximum number of participants that can join the excursion, so that all the participants’ preferences are obeyed and the capacity of the bus is not exceeded.
样例输入
4 41 2 3 4样例输出
4
分析：先求下强连通分量，然后图就变成了树，团或树指向团；
然后对于树或团直接01背包，对于树指向团的可取min——max，背包可用差分优化；
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <unordered_map>#include <queue>#include <stack>#include <ctime>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, ls[rt]#define Rson mid+1, R, rs[rt]#define sys system("pause")#define freopen freopen("in.txt","r",stdin)const int maxn=1e3+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline ll read(){ ll x=0;int f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int n,m,k,t,pre[maxn],link[maxn],sccno[maxn],dfs_clock,scc_cnt,cas,bel1[maxn],pk[maxn],dp[maxn],vis[maxn],sum[maxn];vi e[maxn],to[maxn],bel[maxn];stack<int>s;void bfs(int p){ queue<int>q; for(int x:bel[p])for(int y:to[x])if(sccno[y]!=p)q.push(y),pk[p]++,vis[sccno[y]]++; while(!q.empty()) { int x=q.front(); q.pop(); for(int y:to[x]) { q.push(y); pk[p]++; vis[sccno[y]]=1; } }}void dfs(int u){ pre[u]=link[u]=++dfs_clock; s.push(u); for(int x:e[u]) { if(!pre[x]) { dfs(x); link[u]=min(link[u],link[x]); } else if(!sccno[x]) { link[u]=min(link[u],pre[x]); } } if(link[u]==pre[u]) { scc_cnt++; while(true) { int x=s.top(); s.pop(); sccno[x]=scc_cnt; bel[scc_cnt].pb(x); bel1[scc_cnt]++; if(x==u)break; } }}void find_scc(int n){ dfs_clock=scc_cnt=0; memset(sccno,0,sizeof(sccno)); memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++) if(!pre[i])dfs(i);}int main(){ int i,j; scanf("%d%d",&n,&m); rep(i,1,n) { int a; scanf("%d",&a); e[i].pb(a),to[a].pb(i); } find_scc(n); rep(i,1,scc_cnt){pk[i]=bel1[i];if(bel1[i]!=1)bfs(i);} dp[0]=1; rep(i,1,scc_cnt) { if(vis[i])continue; int x=bel1[i],y=pk[i]; rep(j,1,m)sum[j]=sum[j-1]+dp[j]; for(j=m;j>=1;j--) { if(j<x)break; else if(j>=x&&j<=y)dp[j]=1; else if(sum[j-x]-sum[j-y-1])dp[j]=1; } } for(i=m;dp[i]==0;i--); printf("%d\n",i); //system("Pause"); return 0;}
Outing
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。