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

Re:痛苦ing,交了n次 floyd+2分图 哪里有问题呢 RE疯啦

Posted by newton88518 at 2006-04-07 15:30:52 on Problem 1087
In Reply To:Re:痛苦ing,交了n次 floyd+2分图 哪里有问题呢 RE疯啦 Posted by:newton88518 at 2006-04-07 15:30:12
#include<iostream>
#include<map>
#include<string>
using namespace std;
#define M 500
bool v[M][M];
void floyd(bool x[][M],int lg)
{
	int i,j,k;
	for(k=0;k<lg;k++)
		for(i=0;i<lg;i++)
		{
			if(!x[i][k]) continue;
			for(j=0;j<lg;j++)
			{
				if(!x[k][j]) continue;
				x[i][j]=1;
			}
		}	
}
int match(bool u[][M],int vm1,int vm2)
{
	int* v1=new int [vm1];
	int* v2=new int [vm2];
	int* pre=new int [vm2];
	int* q=new int [vm2];
	memset(v1,-1,vm1*sizeof(int));
	memset(v2,-1,vm2*sizeof(int));
	int i,j,s,e,x,sum=0;
	for(i=0;i<vm1;i++)
	{
		s=e=0;
		for(j=0;j<vm2;j++)
			pre[j]=-2;
		for(j=0;j<vm2;j++)
			if(v[i+vm2+1][j+1]) {
				pre[j]=-1;
				if(v2[j]==-1) 
				{
					x=j;
					goto KML;
				}
				q[e++]=j;
			}
		while(s<e)
		{
			x=q[s];
			if(v2[x]==-1) break;
			s++;
			for(j=0;j<vm2;j++)
			{
				if(pre[j]==-2 && v[v2[x]+vm2+1][j+1])
				{
					pre[j]=x;
					q[e++]=j;
				}
			}
		}
		if(s==e) continue;
		while(pre[x]>-1)
		{
			v1[v2[pre[x]]]=x;
			v2[x]=v2[pre[x]];
			x=pre[x];
		}
KML:	v1[i]=x;
		v2[x]=i;
		sum++;
	}
	delete [] v1;
	delete [] v2;
	delete [] q;
	delete [] pre;
	return sum;
}
void solve()
{
	int n;
	cin>>n;
	int i;
	string s;
	map<string,int> plug;
	map<string,int>::const_iterator p;
	for(i=1;i<=n;i++)
	{
		cin>>s;
		plug[s]=i;
	}
	int m,top;
	cin>>m;
	top=m+n;
	string sde,spg;
	int ns,np;
	pair<string,int> temp;
	for(i=n+1;i<=m+n;i++)
	{
		cin>>sde>>spg;
		if( (p=plug.find(spg))==plug.end() )
		{
			++top;
			plug[spg]=top;
			v[i][top]=1;
		}
		else 
		{
			temp=(*p);
			v[i][temp.second]=1;
		}
	}
	int k,de,pg;
	cin>>k;
	for(i=0;i<k;i++)
	{
		cin>>sde>>spg;
		p=plug.find(sde);
		de=(*p).second;
		p=plug.find(spg);
		pg=(*p).second;
		v[de][pg]=1;
	}
	int start=top+1,end=0;
	for(i=n+1;i<=m+n;i++)
		v[start][i]=1;
	for(i=1;i<=n;i++)
		v[i][end]=1;
	floyd(v,start);
	int sum;
	sum=match(v,m,n);
	cout<<(m-sum)<<endl;
}
int main()
{
//	freopen("a.in","r",stdin);
	solve();
	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