| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:痛苦ing,交了n次 floyd+2分图 哪里有问题呢 RE疯啦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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator