求救一道二分图匹配(会关注的)
查看原帖
求救一道二分图匹配(会关注的)
189181
exit0楼主2021/5/25 21:04

RT,提交结果上显示TLE,但是疑似RE。(从程序时间复杂度理论上来说不会TLE),求助显示TLE的原因?(会关注的)

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 1050
#define M 10000050
using namespace std;
struct Edge{
	int from;
	int to;
	int next;
};
Edge edge[10000010];
int head[N],cnt;
inline void add_Edge(int f,int t)
{
	cnt++;
	edge[cnt].from=f;
	edge[cnt].to=t;
	edge[cnt].next=head[f];
	head[f]=cnt;
}
int matched[N],ans,n;
bool vis[N];
inline bool find(int k)
{
	for(int i=head[k];i;i=edge[i].next)
	{
		int t=edge[i].to;
		if(vis[t])continue;
		vis[t]=1;
		if(!matched[t]||find(matched[t]))
		{
			matched[t]=k;
			return true;
		}
	}
}
inline void match()
{
	
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		if(find(i))ans++;		
	}
}
int a[N],b[N],c[N],d[N],t1,t2,st[N],fi[N],T;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		cnt=0,ans=0;
		memset(head,0,sizeof(head));
		memset(matched,0,sizeof(head));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d:%d%d%d%d%d",&t1,&t2,&a[i],&b[i],&c[i],&d[i]);
			st[i]=t1*60+t2;
			fi[i]=st[i]+abs(a[i]-b[i]+abs(c[i]-d[i]));
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(j==i)continue;
				if(fi[i]+abs(c[i]-a[j])+abs(d[i]-b[j])<st[j])add_Edge(i,j+n);
			}
		}
		match();
		cout<<n-ans<<'\n';
	}	
	return 0;
}
2021/5/25 21:04
加载中...