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 SnowOrld at 2009-02-11 17:21:49 on Problem 3592
我自己试了几组数据,都是对的。提交了总是re,谁看看是哪错了。基本思路就是求强连通图。
#include<iostream>
#include<fstream>
#include<vector>
#include<list>

using namespace std;

fstream input("file.txt");

void dep_first_search(int,int&,vector<vector<int> >::iterator,vector<int>::iterator,vector<bool>::iterator);
void dfs(int,int,vector<vector<int> >::iterator,vector<int>::iterator,vector<bool>::iterator);

int main()
{
	int cases;
	input>>cases;
	for(int m=0;m<cases;++m)
	{
		int x,y;
		input>>x>>y;
		vector<vector<char> > map(x,vector<char>(y,' '));
		int i;
		for(i=0;i<x;++i)
			for(int j=0;j<y;++j)
				input>>map[i][j];
		vector<int> ore(x*y,0);
		vector<int> tmp_vct_int;
		vector<vector<int> > edges(x*y,tmp_vct_int);
		for(i=0;i<x;++i)
		{
			for(int j=0;j<y;++j)
			{
				if(map[i][j]=='#')
					continue;
				if(i<x-1&&map[i+1][j]!='#')
					edges[i*x+j].push_back((i+1)*x+j);
				if(j<y-1&&map[i][j+1]!='#')
					edges[i*x+j].push_back(i*x+j+1);
				if(map[i][j]=='*')
				{
					int m,n;
					input>>m>>n;
					edges[i*x+j].push_back(m*x+n);
				}
				else
				{
					int o=int(map[i][j])-int('0');
					ore[i*x+j]=o;
				}
			}
		}
		vector<int> line(x*y,-1);
		vector<bool> label(x*y,1);
		int count=0;
		dep_first_search(0,count,edges.begin(),line.begin(),label.begin());
		vector<vector<int> > rever_edges(x*y,tmp_vct_int);
		for(i=0;i<x*y;++i)
			for(int k=0;k<edges[i].size();++k)
			{
				int end=edges[i][k];
				rever_edges[end].push_back(i);
			}
		vector<int> queue(count,0);
		for(i=0;i<count;++i)
		{
			for(int j=0;j<x*y;++j)
			{
				if(line[j]==count-i-1)
				{
					queue[i]=j;
					break;
				}
			}
		}
		label.clear();
		label.insert(label.begin(),x*y,1);
		int nd=0;
		vector<int> point(x*y,-1);
		for(i=0;i<count;++i)
		{
			if(label[queue[i]])
			{
				dfs(queue[i],nd,rever_edges.begin(),point.begin(),label.begin());
				++nd;
			}
		}
		vector<int> inter_ore(nd+100,0);
		vector<vector<int> > inter_edges(nd+100,vector<int>(nd+100,0));
		for(i=0;i<x*y;++i)
		{
			if(point[i]==-1)
				continue;
			inter_ore[point[i]]+=ore[i];
			for(int j=0;j<edges[i].size();++j)
			{
				if(point[i]!=point[edges[i][j]])
					inter_edges[point[i]][point[edges[i][j]]]=1;
			}
		}
		vector<int> total_ore(nd+100,0);
		int start=point[0];
		vector<int> process;
		process.push_back(start);
		total_ore[start]=inter_ore[start];
		for(i=0;i<nd;++i)
		{
			vector<int> tmp_pro;
			for(int j=0;j<process.size();++j)
			{
				for(int k=0;k<nd;++k)
				{
					int st=process[j];
					if(inter_edges[st][k])
					{
						if(total_ore[k]<total_ore[st]+inter_ore[k])
						{
							total_ore[k]=total_ore[st]+inter_ore[k];
							tmp_pro.push_back(k);
						}
					}
				}
			}
			process.clear();
			process.insert(process.begin(),tmp_pro.begin(),tmp_pro.end());
		}
		int max=0;
		for(i=0;i<nd;++i)
		{
			if(max<total_ore[i])
				max=total_ore[i];
		}
		cout<<max<<endl;
	}
	return 0;
}

void dep_first_search(int nd,int& count,vector<vector<int> >::iterator edges
					  ,vector<int>::iterator line,vector<bool>::iterator label)
{
	label[nd]=0;
	for(int i=0;i<edges[nd].size();++i)
	{
		int end=edges[nd][i];
		if(label[end])
			dep_first_search(end,count,edges,line,label);
	}
	line[nd]=count;
	++count;
}

void dfs(int nd,int lvl,vector<vector<int> >::iterator edges,vector<int>::iterator point,vector<bool>::iterator label)
{
	label[nd]=0;
	point[nd]=lvl;
	for(int i=0;i<edges[nd].size();++i)
	{
		int end=edges[nd][i];
		if(label[end])
			dfs(end,lvl,edges,point,label);
	}
}


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