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

数据开大点!!!map+网络流,附上代码。。

Posted by ckcz123 at 2013-02-28 18:27:02 on Problem 1087
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;

int father[1020];
int c[1010][1010];
int f[1010][1010];
int l[1010][1010];
int m,n;
bool already[1010];
int times[1010];
int q[1010];
int total;
map<string,int> mymap;
map<string,int>::iterator it;

bool in_flow()
{
	int start=0,end=0;
	int temp;
	memset(already,true,sizeof(already));
	q[0]=0;
	bool e;
	already[0]=false;
	while (start<=end)
	{
		e=false;
		temp=q[start];
		for (int i=1;i<=total+1;i++)
		{
			if (already[i] && l[temp][i]>0)
			{
				end++;
				q[end]=i;
				already[i]=false;
				father[i]=temp;
				if (i==total+1)
				{
					e=true;
					break;
				}
			}
		}
		if (e)
			break;
		start++;
	}
	if (!e)
		return false;
	int k=total+1;
	int minn=99999999;
	while (k!=0)
	{
		if (minn>l[father[k]][k])
			minn=l[father[k]][k];
		k=father[k];
	}
	k=total+1;
	while (k!=0)
	{
		f[father[k]][k]+=minn;
		f[k][father[k]]=-f[father[k]][k];
		l[k][father[k]]=c[k][father[k]]-f[k][father[k]];
		l[father[k]][k]=c[father[k]][k]-f[father[k]][k];
		k=father[k];
	}
	return true;
}

int main()
{
	cin >> m;
	memset(c,0,sizeof(c));
	memset(l,0,sizeof(l));
	memset(f,0,sizeof(f));
	string s;
	total=0;
	int a,b;
	int total1,total2;
	while (m--)
	{
		cin >> s;
		if (mymap.count(s)==0)
		{
			total++;
			mymap.insert(make_pair(s,total));
			times[total]=1;
		}
		else
		{
			it=mymap.find(s);
			times[it->second]++;
		}
	}
	total1=total;
	cin >> m;
	n=m;
	string s1,s2;
	while (m--)
	{
		cin >> s1 >> s2;
		total++;
		mymap.insert(make_pair(s1,total));
		a=total;
		l[0][total]=c[0][total]=1;
		if (mymap.count(s2)==0)
		{
			total++;
			mymap.insert(make_pair(s2,total));
		}
		it=mymap.find(s2);
		b=it->second;
		l[a][b]=c[a][b]=1;
	}
	cin >> m;
	while (m--)
	{
		cin >> s1 >> s2;
		if (mymap.count(s1)==0)
		{
			total++;
			mymap.insert(make_pair(s1,total));
		}
		if (mymap.count(s2)==0)
		{
			total++;
			mymap.insert(make_pair(s2,total));
		}
		it=mymap.find(s1);
		a=it->second;
		it=mymap.find(s2);
		b=it->second;
		l[a][b]=c[a][b]=99999999;
	}
	for (int i=1;i<=total1;i++)
		l[i][total+1]=c[i][total+1]=times[i];
	while (in_flow());
	int sum=0;
	for (int i=1;i<=total;i++)
		if (f[0][i]>0)
			sum+=f[0][i];
	cout << n-sum << endl;
	//system("pause");
	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