Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

发一水代码!!!!

Posted by wocha at 2012-08-20 10:38:04
#include <queue>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#define inf 0x7FFFFFFF
#define M 110
using namespace std;
int end[M*M],edge_num,start[M*M],cost[M*M],next[M*M];
inline void Init(){
	edge_num=0;  memset(start,-1,sizeof(start));
}
void add_edge(int u,int v,int w){
	end[edge_num]=v; cost[edge_num]=w; next[edge_num]=start[u]; start[u]=edge_num++;
}
int vis[M*9],d[M*9],cnt[M*9];
int spfa (int st,int n){
    memset(vis,0,sizeof(vis));   memset(cnt,0,sizeof(cnt));
	for(int i=0;i<=n+5;i++)      d[i]=-inf;
	queue<int> Q;  Q.push(st);   cnt[st]++;  d[st]=0;
	vis[st]=1;  int u,v,w;
	while(!Q.empty()){
		u=Q.front(),Q.pop(),vis[u]=0;
		for(int i=start[u];i!=-1;i=next[i]){
			v=end[i],w=cost[i];
			if(d[v]<d[u]+w){
				d[v]=d[u]+w;
				if(!vis[v]){
					vis[v]=1,Q.push(v);
					if(++cnt[v]>n+1) return 0;
				}
			}
		}
	}
	return 1;
}
int main(){
	int n,m,u,v,w;
	char s[8];
	while(~scanf("%d",&n),n,cin>>m){
		cin>>m;     Init();
		while(m--){
			scanf("%d%d %s %d",&u,&v,s,&w);
			if(s[0]=='g')      add_edge(u-1,u+v,w+1);
			else               add_edge(u+v,u-1,1-w);
		}
	    for(int i=0;i<=n;i++)  add_edge(n+7,i,0);
	    if(spfa(n+7,n))        puts("lamentable kingdom");
	    else                   puts("successful conspiracy");
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator