为啥超时,调了很久了/可怜
  • 板块UVA1411 Ants
  • 楼主JK_LOVER
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/7/24 20:13
  • 上次更新2023/11/6 22:23:06
查看原帖
为啥超时,调了很久了/可怜
227824
JK_LOVER楼主2020/7/24 20:13
#include<bits/stdc++.h>
using namespace std;
const int N = 310;
const int M = N*N;
const int inf = 0x3f3f3f3f;
int read(){
	int x = 0,f = 0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return f?-x:x;
}

struct Edge{int to,nxt,cap,flow;double cost;}e[M<<1];
struct Node{int x,y;}A[N];
int n,cnt=-1,head[N],lastn[N],laste[N],a[N],S,T;
double dist[N];
bool vis[N];
double dis(Node a,Node b)
{
	return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));
}

void add(int x,int y,int cap,double cost)
{
	e[++cnt].cap = cap;e[cnt].flow = 0;
	e[cnt].to = y;e[cnt].cost = cost;
	e[cnt].nxt = head[x];head[x] = cnt; 
}

bool Bfs(int s,int t)
{
	for(int i = 1;i <= t;i++) 
	lastn[i] = laste[i] = a[i] = vis[i] = 0,dist[i] = 1e10;
	queue<int> Q;
	a[s] = inf; dist[s] = 0;
	Q.push(s);vis[s] = 1;
	while(Q.size())
	{
		int x = Q.front();Q.pop();vis[s] = 0;
		for(int i = head[x];~i;i = e[i].nxt)
		{
			int y = e[i].to;
			if(e[i].cap > e[i].flow)
			{
				if(dist[y] > dist[x] + e[i].cost)
				{
					dist[y] = dist[x] + e[i].cost;
					laste[y] = i;
					lastn[y] = x;
					a[y] = min(a[x],e[i].cap - e[i].flow);
					if(vis[y]) continue;
					Q.push(y);
					vis[y] = 1;
				}
			}
		}
	}
	return a[t] > 0;
}

void Ek(int s,int t)
{
	while(Bfs(s,t))
	{
		int k = t;
		while(k != s)
		{
			e[laste[k]].flow += a[t];
			e[laste[k]^1].flow -= a[t];
			k = lastn[k];
		}
	}
}

int main()
{
	while(cin>>n)
	{
		memset(head,-1,sizeof(head));
		cnt = -1;
		S = 2*n+1;T = S+1;
		for(int i = 1;i <= n;i++) scanf("%d %d",&A[i].x,&A[i].y);
		for(int i = 1+n;i <= n*2;i++) scanf("%d %d",&A[i].x,&A[i].y);
		for(int i = 1;i <= n;i++) add(S,i,1,0),add(i,S,0,0);
		for(int i = 1+n;i <= n*2;i++) add(i,T,1,0),add(T,i,0,0);
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1+n;j <= n*2;j++)
			{
				add(i,j,1,dis(A[i],A[j]));
				add(j,i,0,-dis(A[i],A[j]));
			}
		}
		Ek(S,T);
		for(int i = 1;i <= n;i++)
		{
			for(int j = head[i];~j;j=e[j].nxt)
			{
				if(e[j].cap > 0 && e[j].flow == e[j].cap)
				{
					printf("%d\n",e[j].to-n);
					break;
				}
			}
		}
	}
	return 0;
} 
/*
5
-42 58
44 86
7 28
99 34
-13 -59
-47 -44
86 74
68 -75
-68 60
99 -60
*/
2020/7/24 20:13
加载中...