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

心血来潮,用set建了个邻接表,wa了,求指导。。。

Posted by Aidway at 2011-05-09 22:17:11 on Problem 3275
#pragma warning(disable:4786)
#include <iostream>
#include <set>
using namespace std;

const int MAX = 1000 + 5;

int n, m;
int cnt;
set<int> iset[MAX];

void Floyd()
{
	// 枚举每一个点u
	for (int u=1; u<=n; ++u)
	{
		// 对边 u-->v
		for (set<int>::iterator iter1=iset[u].begin(); iter1!=iset[u].end(); ++iter1)
		{
			int v = *iter1;
			// 对边 v-->w
			for (set<int>::iterator iter2=iset[v].begin(); iter2!=iset[v].end(); ++iter2)
			{
				int w = *iter2;
				iset[u].insert(w);	
			}
		}
	}
}

int main()
{
	int i;
	int u, v;

	// 输入数据
	scanf("%d%d", &n, &m);
	for (i=1; i<=m; ++i)
	{
		scanf("%d%d", &u, &v);
		iset[u].insert(v);
	}

	cnt = 0;
	Floyd();	
	// 计算从点i出发的点数
	for (i=1; i<=n; ++i)
	{
		cnt += iset[i].size();
	}

	printf("%d\n", n*(n-1)/2 - cnt);

	return 0;
}

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