Submission #101894

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

int H, W;
int U[100][100], F[100], S[100];

int n0, n1, m, ptr[100], next[20000], zu[20000];
int to[100], fr[100], us[100], total;
int lev[100], que[100], *qb, *qe;

void init(int _n0, int _n1){
	n0 = _n0; n1 = _n1; m = 0; memset(ptr, ~0, n0*4);
}

void ae(int u, int v){
	next[m] = ptr[u];
	ptr[u] = m;
	zu[m] = v;
	++m;
}

int augument(int u) {
	int i, v, w;
	us[u] = total;
	for(i = ptr[u]; ~i; i = next[i]) {
		if(!~(w = fr[v=zu[i]]) || us[w] != total && lev[u] < lev[w] && augument(w)){
			to[u] = v; fr[v] = u; return 1;
		}
	}
	return 0;
}

int solve()
{
	int f, i, u, w;
	memset(to, ~0, n0*4); memset(fr, ~0, n1*4); memset(us, ~0, n1*4);
	for(total=0; ; total+=f){
		qb = qe = que;
		memset(lev, ~0, n0*4);
		for(u=0; u<n0; ++u) if(!~to[u]) lev[*qe++ = u] = 0;
		for(;qb!=qe;) for(i = ptr[u = *qb++]; ~i; i = next[i]){
			if(~(w = fr[zu[i]]) && !~lev[w]) lev[*qe++ = w] = lev[u] + 1;
		}
		for(f=0, u=0; u<n0; ++u) if(!~to[u]) f += augument(u);
		if(!f) return total;
	}
	return -1;
}

int solve(int h)
{
	//takasa h ni tsuite toku
	bool valid[100][100];
	int vc = 0;

	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			valid[i][j] = (U[i][j]==1);
			if(F[j] < h || S[i] < h) valid[i][j] = 0;
			if(F[j] > h && S[i] > h) valid[i][j] = 0;

			if(valid[i][j]) ++vc;
		}
	}

	int reqr = 0;
	for(int i=0;i<H;i++) if(S[i]==h){
		++reqr;

		bool flg = false;
		for(int j=0;j<W;j++) if(valid[i][j]) flg = true;

		if(!flg) return -10000000;
	}
	for(int j=0;j<W;j++) if(F[j]==h){
		++reqr;

		bool flg = false;
		for(int i=0;i<H;i++) if(valid[i][j]) flg = true;

		if(!flg) return -10000000;

	}
	
	init(H, W);
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++) if(S[i]==h && F[j]==h && valid[i][j]) ae(i, j);

	int tmp = reqr - solve();
	return tmp * h + (vc - tmp);
}

int main()
{
	scanf("%d%d", &H, &W);
	for(int i=0;i<H;i++)
		for(int j=0;j<W;j++) scanf("%d", &(U[i][j]));
	for(int i=0;i<W;i++) scanf("%d", F+i);
	for(int i=0;i<H;i++) scanf("%d", S+i);

	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(S[i]==0 || F[j]==0){
				if(U[i][j]==1){
					puts("-1");
					return 0;
				}
			}
		}
	}

	int ret = 0;
	for(int i=100;i>0;i--){
		//printf("%d %d\n", i, solve(i));
		ret += solve(i);
		if(ret < 0){
			puts("-1");
			return 0;
		}
	}

	printf("%d\n", ret);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:97: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:99: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:100: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:101: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result