Submission #478185

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define SIZE 210
#define INF 1000000000

using namespace std;

struct MaxFlow
{
	struct edge
	{
		int to,cap,rev;
		edge(int t,int c,int r)
		{
			to=t;
			cap=c;
			rev=r;
		}
	};
	vector <edge> vec[SIZE];
	bool use[SIZE];
	
	void init()
	{
		for(int i=0;i<SIZE;i++)
		{
			vec[i].clear();
		}
	}
	void add(int start,int end,int cap)
	{
		int s=vec[start].size(),e=vec[end].size();
		vec[start].push_back(edge(end,cap,e));
		vec[end].push_back(edge(start,0,s));
	}
	int dfs(int v,int t,int f)
	{
		if(v==t) return f;
		use[v]=true;
		for(int i=0;i<vec[v].size();i++)
		{
			edge &e=vec[v][i];
			if(!use[e.to]&&e.cap>0)
			{
				int d=dfs(e.to,t,min(f,e.cap));
				if(d>0)
				{
					e.cap-=d;
					vec[e.to][e.rev].cap+=d;
					return d;
				}
			}
		}
		return 0;
	}
	int max_flow(int s,int t)
	{
		int flow=0;
		while(1)
		{
			memset(use,false,sizeof(use));
			int f=dfs(s,t,INF);
			if(f==0) return flow;
			flow+=f;
		}
	}
};
MaxFlow solve;
int mp[SIZE][SIZE];
int f[SIZE],s[SIZE];

int main()
{
	int h,w;
	scanf("%d %d",&h,&w);
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			scanf("%d",&mp[i][j]);
		}
	}
	for(int i=0;i<w;i++) scanf("%d",&f[i]);
	for(int i=0;i<h;i++) scanf("%d",&s[i]);
	int ret=0;
	for(int i=0;i<w;i++) ret+=max(f[i]-1,0);
	for(int i=0;i<h;i++) ret+=max(s[i]-1,0);
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			ret+=mp[i][j];
			if(mp[i][j]==1&&(f[i]==0||s[i]==0))
			{
				puts("-1");
				return 0;
			}
		}
	}
	for(int k=SIZE;k>=1;k--)
	{
		vector <int> vw,vh;
		for(int i=0;i<w;i++) if(f[i]==k) vw.push_back(i);
		for(int i=0;i<h;i++) if(s[i]==k) vh.push_back(i);
		if(vw.empty()&&vh.empty()) continue;
		int S=vw.size()+vh.size(),T=S+1;
		solve.init();
		for(int i=0;i<vh.size();i++)
		{
			for(int j=0;j<vw.size();j++)
			{
				int x=vh[i],y=vw[j];
				if(mp[x][y]==1)
				{
					solve.add(i,j+vh.size(),1);
				}
			}
		}
		for(int i=0;i<vh.size();i++)
		{
			int x=vh[i];
			bool up=false;
			for(int j=0;j<w;j++)
			{
				if(f[j]>=k&&mp[x][j]==1)
				{
					up=true;
					break;
				}
			}
			if(!up)
			{
				puts("-1");
				return 0;
			}
		}
		for(int i=0;i<vw.size();i++)
		{
			int y=vw[i];
			bool up=false;
			for(int j=0;j<h;j++)
			{
				if(s[j]>=k&&mp[j][y]==1)
				{
					up=true;
					break;
				}
			}
			if(!up)
			{
				puts("-1");
				return 0;
			}
		}
		for(int i=0;i<vh.size();i++) solve.add(S,i,1);
		for(int i=0;i<vw.size();i++) solve.add(i+vh.size(),T,1);
		int gt=solve.max_flow(S,T);
		ret-=gt*(k-1);
	}
	printf("%d\n",ret);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:79: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:84: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:87: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:88: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result