想的时间比较长所以看题解了= =
原题:
Fj有N(N<=1000)头牛,每头牛都有独一无二的正整数 魅力值,Fj想让他们按
魅力值排序。
Fj已经知道M(1<=M<=10000)对奶牛的魅力值,但他发现,他还需要再做一张关
于另外C对奶牛的魅力值比较,才能推断出所有奶牛的魅力值的顺序。
现在请你帮他 算出最小的C值。
刚在拓扑排序方向上想,思路是每次选一个入度为0的点,让这个点向其它所有入度为0的点连边,然后这个点就是目前最高点了,然后就可以删掉不管了,所以可以直接删掉这个点
为了保证最坏情况所以每次删掉的点是所有入度为0的点中从这个点出发能到达的点最多的点
然后用堆搞一下,发现答案不对?
手玩小数据没问题,想了将近一下午无果,遵循经很多神犇"想的时间太长就不要再想"的建议,选择看题解
正解是用减法原理,确定完整的关系需要知道n*(n-1)/2条关系,已知的关系就是每个点能到达的点的个数的和,dfs搞一搞就可以了
然后遇到两个小问题,就是下面这两个dfs都是不对的:
/*void dfs(int x){注意这样可能会有重复的
f[x]=1;
for(int i=LINK[x];i;i=e[i].next){
if(!f[e[i].y]) dfs(e[i].y);
f[x]+=f[e[i].y];
}
}*/
/*int dfs(int x){这样也可能会有重复的
int z=1;
for(int i=LINK[x];i;i=e[i].next) z+=dfs(e[i].y);
return z;
}*/
反例很简单,请自己手玩
代码(我直接在原来堆的错误写法上改的,有一个堆还有各种乱搞,所以代码比较长= =):
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){int z=,mark=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mark=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mark;
}
struct ddd{int next,y;}e[]; int LINK[],ltop=,rd[],cd[];
inline void insert(int x,int y){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;cd[x]++;rd[y]++;}
int n,m;
//int QUEUE[1100000],head=0;
int ans=;
bool flag[];
int f[];
int visited[];
int max_heap[],size=;
void push(int x){
max_heap[size]=x;
int current=size,father=(size-)>>;
while(f[max_heap[current]]>f[max_heap[father]] && father>=){
swap(max_heap[current],max_heap[father]);
current=father,father=(current-)>>;
}
size++;
}
void updata(int x){
int lchild=(x<<)+,rchild=(x<<)+;
int max_id=x;
if(lchild<size && f[max_heap[lchild]]>f[max_heap[max_id]]) max_id=lchild;
if(rchild<size && f[max_heap[rchild]]>f[max_heap[max_id]]) max_id=rchild;
if(max_id!=x){
swap(max_heap[x],max_heap[max_id]);
updata(max_id);
}
}
void pop(){
swap(max_heap[],max_heap[size-]);
size--;
updata();
}
/*void dfs(int x){注意这样可能会有重复的:(1,2),(3,2)
f[x]=1;
for(int i=LINK[x];i;i=e[i].next){
if(!f[e[i].y]) dfs(e[i].y);
f[x]+=f[e[i].y];
}
}*/
/*int dfs(int x){这样也可能会有重复的,比如(1,2),(2,3),(1,3)
int z=1;
for(int i=LINK[x];i;i=e[i].next) z+=dfs(e[i].y);
return z;
}*/
int dfs(int x,int y){
int z=;
for(int i=LINK[x];i;i=e[i].next)if(visited[e[i].y]!=y){
visited[e[i].y]=y;
z+=dfs(e[i].y,y);
}
return z;
}
int main(){//freopen("ddd.in","r",stdin);
memset(flag,,sizeof(flag));
cin>>n>>m;
int _left,_right;
while(m --> ){//趋向于
_left=read(),_right=read();
insert(_left,_right);
}
//for(int i=1;i<=n;++i)if(!rd[i]) QUEUE[++head]=i,++cnt;
for(int i=;i<=n;++i) ans+=dfs(i,i)-;
//for(int i=1;i<=n;++i)if(!rd[i]) push(i);
/*for(int i=1;i<=n;++i){
cout<<rd[max_heap[0]]<<endl;
pop();
}*/
/*while(size){
//cout<<ans<<" "<<cnt<<endl;
ans+=size-1;
int max_id=max_heap[0]; pop();
for(int i=LINK[max_id];i;i=e[i].next){
rd[e[i].y]--;
if(!rd[e[i].y]) push(e[i].y);
}
//cout<<max_id<<endl;
}*/
cout<<n*(n-)/-ans<<endl;
return ;
}