3037: 创世纪
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 123 Solved: 66
[Submit][Status]
Description
applepi手里有一本书《创世纪》，里面记录了这样一个故事……
上帝手中有着N 种被称作“世界元素”的东西，现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素，所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它，这样上帝就可以保持对世界的控制。
由于那个著名的有关于上帝能不能制造一块连自己都不能举起的大石头的二律背反命题，我们知道上帝不是万能的，而且不但不是万能的，他甚至有事情需要找你帮忙——上帝希望知道他最多可以投放多少种世界元素，但是他只会O(2^N) 级别的算法。虽然上帝拥有无限多的时间，但是他也是个急性子。你需要帮助上帝解决这个问题。
Input
第一行是一个整数N，表示世界元素的数目。
第二行有 N 个整数A1, A2, …, AN。Ai 表示第i 个世界元素能够限制的世界元素的编号。
Output
一个整数，表示最多可以投放的世界元素的数目。
Sample Input
2 3 1 3 6 5
Sample Output
HINT
样例说明
选择2、3、5 三个世界元素即可。分别有1、4、6 来限制它们。
数据范围与约定
对于30% 的数据，N≤10。
对于60% 的数据, N≤10^5。
对于 100% 的数据，N≤10^6，1≤Ai≤N，Ai≠i。
Source
题目大意：给定一张有向图，每个点有且仅有一条出边，要求若一个点x扔下去，至少存在一个保留的点y，y的出边指向x，求最多扔下去多少个点
首先原题的意思就是支配关系 我们反向考虑 求最少保留的点 要求一个点若扔出去 则必须存在一个保留的点指向它
于是这就是最小支配集 不过由于是有向图 所以一个点要么选择 要么被子节点支配 所以就只剩下2个状态了
设f[x]为以x为根的子树选择x的最小支配集 g[x]为不选择x的最小支配集
然后由于是基环树林 所以我们选择一个环上的点 拆掉它的出边 设这个点为x 出边指向的点为y 讨论
1.若x选择 则y一开始就是被支配状态 g[y]初值为0 求一遍最小支配集
2.若x不选 正常求最小支配集即可
两种情况取最小值计入ans 最后输出n-ans即可
然后说一下我关于这张图的形态的理解:
因为原本每个点只有一个出度，入度不定，然后n条边，就是一个 内向树 （直觉上。。。）（用词不专业，不知道对不对。。。）
然后我们存的时候是反过来存的 存每个点能够被哪几个点支配，这样就成了入度为1，出度不定了，就成了一个外向树
所以我们随便找到环上的一个点，然后就可以遍历到所有点。。。而我们找环的时候是顺着原来的边找的，因为这样在环的分叉上回到环。
而这个过程使得一些点没有被标记，所以在DP的时候还要加标记
一些注释写在代码里：
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 1000000+100 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26 int x=0,f=1;char ch=getchar(); 27 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 28 while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();} 29 return x*f; 30 } 31 int n,rt,ban,ans,a[maxn],fa[maxn],head[maxn],f[maxn],g[maxn]; 32 bool v[maxn]; 33 struct edge{int go,next;}e[maxn]; 34 inline void dfs(int x) 35 { 36 v[x]=1; 37 if(v[a[x]])rt=x;else dfs(a[x]); 38 } 39 inline void dp(int x) 40 { 41 f[x]=1;g[x]=inf;v[x]=1; 42 if(x==ban)g[x]=0; 43 for(int i=head[x];i;i=e[i].next) 44 if(i!=rt&&e[i].go!=fa[x]) 45 { 46 int y=e[i].go; 47 fa[y]=x; 48 dp(y); 49 g[x]+=min(f[y],g[y]); 50 g[x]=min(g[x],f[x]+f[y]-1);//这里巧妙的避免了使用临时变量来存储f[y]与g[y]的最小差值 51 f[x]+=min(f[y],g[y]); 52 } 53 } 54 int main() 55 { 56 freopen("input.txt","r",stdin); 57 freopen("output.txt","w",stdout); 58 n=read();int x; 59 for1(i,n)e[i].go=i,a[i]=x=read(),e[i].next=head[x],head[x]=i; 60 for1(i,n) 61 if(!v[i]) 62 { 63 dfs(i);//找出这棵基环树 64 ban=a[rt];//选取rt作为x，a[rt]作为y，g[y]=0 65 dp(rt); 66 int tmp=f[rt];//限定rt必须选 67 ban=0; 68 dp(rt); 69 tmp=min(tmp,g[rt]);//不用选rt 70 ans+=tmp; 71 } 72 printf("%d ",n-ans); 73 return 0; 74 }