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

菜鸟贴个代码备忘 请大家忽略

Posted by songruirui at 2013-05-16 16:02:23 on Problem 1149
#include <iostream>
#include <queue>
using namespace std;
const int _housenum=1001;
const int _cusnum=101;
const int _inf=9000000;
int cnt;
int head[_housenum];
bool table[_cusnum][_housenum];
struct _edge
{
	int head;
	int nx;
	int ver;
	int remain;
};
_edge edge[30000];
int hsnum;//housenum
int csnum;//customernum
int demand[_cusnum];
int fa[_cusnum+_housenum+10];
int glstep;
struct node
{
	int step;
	int ver;
};
bool vis[_cusnum+_housenum+10];
void add_edge(int s,int t,int val)
{
	cnt++;
	edge[cnt].nx=head[s];
	edge[cnt].ver=t;
	edge[cnt].remain=val;
	edge[cnt].head=s;
	head[s]=cnt;
}
bool glflag=false;
void dfs(int curedge,int step)
{	
	//vis[edge[curedge].head]=true;
	vis[edge[curedge].ver]=true;
	fa[step]=curedge;
	if(edge[curedge].ver==csnum+hsnum+1)
	{
		glflag=true;
		glstep=step;
		return;
	}
	int nx=head[edge[curedge].ver];
	int cur;
	
	while(nx!=0&&glflag==false)
	{
		cur=edge[nx].ver;
		if(vis[cur]==false&&edge[nx].remain>0)
			dfs(nx,step+1);
		nx=edge[nx].nx;
	}
} 

int solve()
{

	glflag=false;
	vis[0]=true;
	for(int i=1;i<=csnum+hsnum+1;i++)
	{
		vis[i]=false;
	}
	int minflow;
	while(true)
	{
		int nx=head[0];
		while(nx!=0&&glflag==false)
		{
			if(edge[nx].remain>0&&vis[edge[nx].ver]==false)
				dfs(nx,1);
			nx=edge[nx].nx;
		}
		if(vis[csnum+hsnum+1]==false)
			break;
		minflow=_inf;
		
		for(int i=1;i<=glstep;i++)
		{
			minflow=min(minflow,edge[fa[i]].remain);
		}
		for(int i=1;i<=glstep;i++)
		{
			edge[fa[i]].remain-=minflow;
			//edge[(fa[i]+1)^1].remain+=minflow;
			if(fa[i]%2==0)
				edge[fa[i]-1].remain+=minflow;
			else
				edge[fa[i]+1].remain+=minflow;
		}
		for(int i=1;i<=csnum+hsnum+1;i++)
		{
			vis[i]=false;
		}
		glflag=false;
	}
	int nx=head[0];
	int sum=0;
	while(nx!=0)
	{
		sum+=edge[nx].remain;
		nx=edge[nx].nx;
	}
	return sum;
}
int main()
{
	cin>>hsnum>>csnum;
	int pignum;
	int totalpig=0;
	for(int i=1;i<=hsnum;i++)
	{	
		cin>>pignum;
		totalpig+=pignum;
		add_edge(0,i,pignum);
		add_edge(i,0,0);
	}
	int keynum,key;
	for(int i=1;i<=csnum;i++)
	{
		cin>>keynum;
		for(int j=1;j<=keynum;j++)
		{
			cin>>key;	
			table[i][key]=true;
			add_edge(key,i+hsnum,_inf);
			add_edge(i+hsnum,key,0);
			for(int k=1;k<i;k++)
			{
				if(table[k][key]==true)
				{
					add_edge(k+hsnum,i+hsnum,_inf);
					add_edge(i+hsnum,k+hsnum,0);
				}
			}
		}
		cin>>demand[i];
		add_edge(i+hsnum,hsnum+csnum+1,demand[i]);
		add_edge(hsnum+csnum+1,i+hsnum,0);
	}
	int re=solve();//最大流
	cout<<totalpig-re<<endl;
	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