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

Re:和zoj1994一样的。。。为啥在poj过了在zoj就WA了

Posted by zheng657555102 at 2013-07-21 15:01:09 on Problem 2396
In Reply To:和zoj1994一样的。。。为啥在poj过了在zoj就WA了 Posted by:zheng657555102 at 2013-07-21 15:00:34
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <list>
#include <algorithm>
using namespace std;
#define N 250
#define M 4444
#define INF 0x3f3f3f3f
int n,m;
int resflow[N][N];
int level[N];
bool isVisited[N];
int row[N],col[N];
int up[N][N],down[N][N];
int in[N],out[N];
int ST,ED;
int scr,sink;
bool flag;
void init()
{
	memset(resflow,0,sizeof(resflow));
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	memset(down,0,sizeof(down));
	memset(up,INF,sizeof(up));
}
int firstOut(int x)
{
	for(int i=ST;i<=ED;i++)
		if(resflow[x][i]!=0&&level[i]==level[x]+1)
			return i;
	return -1;
}

int bfs()
{
	int i;
	bool flag=0;
	queue<int> q;
	memset(level,INF,sizeof(level));
	memset(isVisited,0,sizeof(isVisited));
	q.push(scr);
	level[scr]=0;
	isVisited[scr]=true;
	while(!q.empty())
	{
		int temp=q.front();
		q.pop();
		for(i=ST;i<=ED;i++)
			if(resflow[temp][i]!=0&&!isVisited[i])
			{
				isVisited[i]=true;
				level[i]=level[temp]+1;
				q.push(i);
			}
		if(temp==sink) flag=true;
	}
	return flag;
}
int dinic()
{
	int u,v,capflow,last;
	list<int> path;
	list<int>::iterator its;
	int maxflow=0;
	while(bfs())
	{
		path.clear();
		path.push_back(scr);
		while(firstOut(scr)!=-1)
		{
			u=path.back();
			if(u!=sink)
			{
				v=firstOut(u);
				if(v>=0)
					path.push_back(v);
				else
				{
					path.pop_back();
					level[u]=INF;
				}
			}
			else
			{
				capflow=INF;
				for(its=path.begin();its!=path.end();its++)
				{
					u=*its;
					if((++its)==path.end())
						break;
					v=*its;
					if(resflow[u][v]<capflow)
						capflow=resflow[u][v];
					--its;
				}
				last=-1;
				maxflow+=capflow;
				for(its=path.begin();its!=path.end();its++)
				{
					u=*its;
					if((++its)==path.end())
						break;
					v=*its;
					resflow[u][v]-=capflow;
					resflow[v][u]+=capflow;
					if(resflow[u][v]==0&&last==-1)
						last=u;
					--its;
				}
				while(path.back()!=last)
					path.pop_back();
			}
		}
	}
	return maxflow;
}
inline void insert(int u,int v,char ch,int val)
{

	if(ch=='=')
	{
		if(down[u][v]>val || up[u][v]<val) flag=true;
		up[u][v]=down[u][v]=val;
	}
	if(ch=='<')
		up[u][v]=min(up[u][v],val-1);
	if(ch=='>')
		down[u][v]=max(down[u][v],val+1);
	if(up[u][v]<down[u][v]) flag=true;
}
int main()
{
	int T,c;
	scanf("%d",&T);
	while(T--)
	{
		init();
		scanf("%d%d",&m,&n);
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&row[i]);
			up[0][i]=down[0][i]=row[i];
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&col[i]);
			up[i+m][m+n+1]=down[i+m][m+n+1]=col[i];
		}
		scanf("%d",&c);
		flag=false;
		while(c--)
		{
			int a,b,val;
			char ch[3];
			scanf("%d%d%s%d",&a,&b,ch,&val);
			if(ch[0]=='=')
				if(val<0) flag=true;
			else if(ch[0]=='>')
				if(val<0) val=-1;
			else if(ch[0]=='<')
				if(val<=0) flag=true;
			if(a==0 && b!=0)
			{
				for(int i=1;i<=m;i++)
					insert(i,m+b,ch[0],val);
			}
			else if(a!=0 && b==0)
			{
				for(int i=1;i<=n;i++)
					insert(a,m+i,ch[0],val);
			}
			else if(a==0 && b==0)
			{
				for(int i=1;i<=m;i++)
					for(int j=1;j<=n;j++)
						insert(i,m+j,ch[0],val);
			}
			else 
				insert(a,m+b,ch[0],val);
		}
		if(flag)
		{
			printf("IMPOSSIBLE\n");
			continue;
		}
		for(int i=1;i<=m;i++)
		{
			resflow[0][i]=0;
			in[i]+=down[0][i];
			out[0]+=down[0][i];
		}
		for(int i=m+1;i<=m+n;i++)
		{
			resflow[i][m+n+1]=0;
			out[i]+=down[i][m+n+1];
			in[m+n+1]+=down[i][m+n+1];
		}
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
			{
				resflow[i][m+j]=up[i][m+j]-down[i][m+j];
				out[i]+=down[i][m+j];
				in[m+j]+=down[i][m+j];
			}
		resflow[m+n+1][0]=INF;
		int sum=0;
		for(int i=0;i<=n+m+1;i++)
		{
			int d=in[i]-out[i];
			if(d>0)
			{
				resflow[m+n+2][i]=d;
				sum+=d;
			}
			else
				resflow[i][m+n+3]=-d;
		}
		scr=m+n+2;sink=m+n+3;
		ST=0;ED=n+m+3;
		int temp=dinic();
		if(sum==temp)
		{
			for(int i=1;i<=m;i++)
			{
				for(int j=1;j<=n;j++)
				{
					cout<<up[i][m+j]-resflow[i][j+m];
					if(j<n) cout<<" ";
				}
				cout<<endl;
			}
		}
		else
			printf("IMPOSSIBLE\n");
		if(T) puts("");
	}
	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