POI - PA 2008 Studies [A] [Graph]

02-04-10   08:12       Studies [A]      OK           10                                                      .





題目是說

給你一張有向有權圖  V<=300  E<=90000

如果點A能經過一條路徑(可經過重複邊重複點)回到自己 那他就是好的點

請輸出所有好的點









SCC，因為非SCC以外的點絕對沒有影響

全部cost反過來，鈴鐺人只要有負圈就表示這個SCC都可以

(原圖存在正圈)


//*********************************

#include<stdio.h>
#include<algorithm>
#define INF 10000000000LL
int color[400], n, m, cCnt, stamp[400], a, b, tt, conv[400], bfCnt, cnt, out[400];
long long c, dist[400];
struct edge{
	int i, j;
	long long co;
	edge *next;
}e[200000], *v[400], *vr[400], e_bf[200000];
bool vis[400], visr[400], canScc[400];
void set(edge **vv, edge *ee, int i, int j, long long c){
	edge *p=vv[i];
	vv[i]=ee; ee->i=i; ee->j=j; ee->co=c; ee->next=p;
}
void dfs(int n){
	vis[n]= 1;
	for(edge *p=v[n]; p; p=p->next)
		if(!vis[p->j]){
			dfs(p->j);
		}
	stamp[++tt]= n;
}
void dfsr(int n){
	visr[n]= 1;
	for(edge *p=vr[n]; p; p=p->next){
		if(!visr[p->j]){
			color[p->j]= color[n];
			dfsr(p->j);
		}
	}
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i=0; i<m; i++){
		scanf("%d%d%lld", &a, &b, &c);
		set(v, e+i, a, b, -c);
		set(vr, e+i+m, b, a, -c);
	}
	for(int i=1; i<=n; i++){
		dist[i]= INF;
		if(!vis[i])
			dfs(i);
	}
	for(int z=tt; z>0; z--){
		int i= stamp[z];
		if(!visr[i]){
			color[i]= ++cCnt;
			conv[cCnt]= i;
			dist[i]= 0;
			dfsr(i);
		}
	}
	for(int i=0; i<m; i++)
		if(color[e[i].i]== color[e[i].j])
			e_bf[bfCnt++]= e[i];
	for(int z=1; z<n; z++)
		for(int i=0; i<bfCnt; i++)
			if(dist[e_bf[i].j]> dist[e_bf[i].i]+e_bf[i].co)
				dist[e_bf[i].j]= dist[e_bf[i].i]+e_bf[i].co;
	for(int i=0; i<bfCnt; i++)
		if(dist[e_bf[i].j]> dist[e_bf[i].i]+e_bf[i].co)
			canScc[color[e_bf[i].i]]= 1;
	for(int i=1; i<=n; i++)
		if(canScc[color[i]])
			out[cnt++]= i;
	printf("%d\n", cnt);
	for(int i=0; i<cnt; i++, putchar(i==cnt?'\n':' '))
		printf("%d", out[i]);
}