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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

用递归写的dinic应该不比用栈模拟的更差啊,但是为啥还是超时啊?

Posted by 578141611 at 2012-12-29 20:55:45 on Problem 3189
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
using namespace std;

#define inf 10000000
#define N 4010
#define M 200

struct edge
{
	int sta;
	int end;
	int cap;
	int next;
}E[N*M*2];
int edgenum,head[N+M],restmp;
int dis[N];
int rank[N][M],numb[M];
int n,b;
void init()
{
	edgenum=0;
	memset(head,-1,sizeof(head));
}
void addedge(int sta,int end,int cap)
{
	E[edgenum].sta=sta;
	E[edgenum].end=end;
	E[edgenum].cap=cap;
	E[edgenum].next=head[sta];
	head[sta]=edgenum++;
}
void build(int sta,int end,int low,int high)
{
	int i,j;
	init();
	for(i=1;i<=n;i++)
	{
		addedge(sta,i,1);
		addedge(i,sta,0);
	}
	for(i=n+1;i<=n+b;i++)
	{
		addedge(i,end,numb[i-n]);
		addedge(end,i,0);
	}
	for(i=1;i<=n;i++)
	{
		for(j=low;j<=high;j++)
		{
			addedge(i,n+rank[i][j],inf);
			addedge(n+rank[i][j],i,0);
		}
	}
}
int BFS(int sta,int end)
{
	queue<int>que;
	memset(dis,0,sizeof(dis));
	que.push(sta);
	dis[sta]=1;
	while(!que.empty())
	{
		int front=que.front();
		que.pop();
		if(front==end)return 1;
		for(int i=head[front];i!=-1;i=E[i].next)
		{
			int to=E[i].end;
			if(E[i].cap>0&&dis[to]==0)
			{
				que.push(to);
				dis[to]=dis[front]+1;
			}
		}
	}
	return 0;
}
int DFS(int sta,int end,int cur,int minx)
{
	if(cur==end)
	{
		restmp+=minx;
		return minx;
	}
	for(int i=head[cur];i!=-1;i=E[i].next)
	{
		if(E[i].cap>0&&dis[E[i].end]==dis[cur]+1)
		{
			int t=DFS(sta,end,E[i].end,min(minx,E[i].cap));
			if(t>0)
			{
				E[i].cap-=t;
				E[i^1].cap+=t;
				if(cur!=sta)return t;
			}
		}
	}
	return 0;
}
int dinic(int sta,int end,int low,int high)
{
	int flow=0;
	build(sta,end,low,high);
	while(BFS(sta,end))
	{
		restmp=0;
		DFS(sta,end,sta,inf);
		if(restmp==0)break;
		flow+=restmp;
	}
	return flow==n;
}
int erfen(int sta,int end)
{
	int left=1,right=1;
	int mid,i;
	while(left<=right&&right<=b)
	{
		mid=(left+right)/2;
		int ff=0;
		for(i=1;i<=b-mid+1;i++)
		{
			if(dinic(sta,end,i,i+mid-1))
			{
				ff=1;
				break;
			}
		}
		if(ff)
			right=mid-1;
		else
			left=mid+1;
	}
	return left;
}
int main()
{
	scanf("%d%d",&n,&b);
	{
		int i,j;
		int sta=0,end=n+b+1;//源点和汇点
		for( i=1;i<=n;i++)
		{
			for( j=1;j<=b;j++)
				scanf("%d",&rank[i][j]);
		}
		for(i=1;i<=b;i++)
			scanf("%d",&numb[i]);
		printf("%d\n",erfen(sta,end));
	}
	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