记录编号	467480	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]奖学金	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.119 s
提交时间	2017-10-30 17:50:12	内存使用	17.47 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f
using namespace std;
const int maxn=100000;
int n,m,h,ans,q[maxn],vis[maxn],dis[maxn],cnt[maxn];
vector<pair<int,int> >p[maxn];
bool flag;
void spfa(int x){
	vis[x]=1,q[++h]=x;
	while(h){
		int u=q[h];h--,vis[u]=0;
		for(int i=0;i<(int)p[u].size();i++){
			int v=p[u][i].first;
			if(dis[v]<dis[u]+p[u][i].second){
				dis[v]=dis[u]+p[u][i].second;
				if(!vis[v]){
					vis[v]=1,q[++h]=v,cnt[v]++;
					if(cnt[v]>n+1){flag=1;return;}
				}
			}
		}
	}
}
int main(){
	freopen("reward.in","r",stdin);
	freopen("reward.out","w",stdout);
	scanf("%d%d",&n,&m);
	int a,b,maxx=0;
	for(int i=1;i<=m;i++)scanf("%d%d",&a,&b),p[b].push_back(make_pair(a,1));
	for(int i=1;i<=n;i++)p[0].push_back(make_pair(i,100));
	spfa(0);
	if(flag){printf("impossible");return 0;}
	for(int i=1;i<=n;i++)ans+=dis[i];
	printf("%d",ans);
	return 0;
}