Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 用递归写的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 dis[N];
int rank[N][M],numb[M];
int n,b;
void init()
{
edgenum=0;
}
{
E[edgenum].sta=sta;
E[edgenum].end=end;
E[edgenum].cap=cap;
}
void build(int sta,int end,int low,int high)
{
int i,j;
init();
for(i=1;i<=n;i++)
{
}
for(i=n+1;i<=n+b;i++)
{
}
for(i=1;i<=n;i++)
{
for(j=low;j<=high;j++)
{
}
}
}
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;
{
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;
}
{
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: