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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

求救,TLE了,在discuss上一个差不多的模板过了

Posted by zl_leaf at 2012-04-19 13:55:50 on Problem 1459
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<memory.h>
#include<queue>
#include<cstdio>
#include <cmath>

using namespace std;

#define MAXN 110
#define INF 999999999
int n,np,nc,m;
int cap[MAXN][MAXN],father[MAXN],res;
int start,end;
queue<int>q;

void maxflow()
{
	int x,i,temp,ok;
	
	while(1)
	{
		ok=0;
		for(i=0;i<=end;i++)
			father[i]=-1;
		
		q.push(start);
		temp=INF;
		while(!q.empty())
		{
			x=q.front();
			q.pop();
			for(i=0;i<=end;i++)
			{
				if(father[i]==-1&&cap[x][i]>0)
				{
					if(i==end)
						ok=1;
					father[i]=x;
					temp=temp<cap[x][i]?temp:cap[x][i];
					
					q.push(i);
				}
			}
		}
		if(!ok)  break;
		
		for(i=end;i!=0;i=father[i])
		{
			cap[father[i]][i]-=temp;
			cap[i][father[i]]+=temp;
		}
		res+=temp;
	}
	return ;
}

int main()
{
	int i,j,a,b,c;
	char s[30];
	while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
	{
		start=0;
		end=n+1;
		for(i=0;i<=end;i++)
			for(j=0;j<=end;j++)
				cap[i][j]=0;
		for(i=0;i<m;i++)
		{
			scanf("%s",s);
			sscanf(s,"(%d,%d)%d",&a,&b,&c);
			cap[a+1][b+1]+=c;
		}
		for(i=0;i<np;i++)
		{
			scanf("%s",s);
			sscanf(s,"(%d)%d",&a,&b);
			cap[start][a+1]+=b;
		}
		for(i=0;i<nc;i++)
		{
			scanf("%s",s);
			sscanf(s,"(%d)%d",&a,&b);
			cap[a+1][end]+=b;
		}
		res=0;
		maxflow();
		printf("%d\n",res);
	}
	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