Submission #1411763

---

Source Code Expand

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define SIZE 500
#define INF 1000000
typedef pair<int, int>pii;
class maxflow
{
public:
	vector<int>pat[SIZE];
	vector<int>cap[SIZE];
	vector<int>rev[SIZE];
	bool flag[SIZE];
	int dist[SIZE];
	int now[SIZE], ind[SIZE];
	int idx[SIZE];
	int flow;
	int gd;
	void adde(int s, int t, int cp)//多重辺は消してから s->tの容量cpの辺をはる
	{
		pat[s].push_back(t);
		pat[t].push_back(s);
		cap[s].push_back(cp);
		cap[t].push_back(0);
		rev[s].push_back(pat[t].size() - 1);
		rev[t].push_back(pat[s].size() - 1);
	}
	void blockflow(int node, int len, int go, int pt)//ブロックフローを求めて流す
	{
		if (pt == len)
		{
			if (node != go)return;
			int mini = INF, rr = -1;
			for (int i = 0; i < pt; i++)if (cap[now[i]][ind[i]] < mini)mini = cap[now[i]][ind[i]], rr = i;
			for (int i = 0; i < pt; i++)cap[now[i]][ind[i]] -= mini, cap[pat[now[i]][ind[i]]][rev[now[i]][ind[i]]] += mini;
			flow += mini;//mini==INFになったら非有界
			gd = rr;
			return;
		}
		now[pt] = node;
		for (int i = idx[node]; i < pat[node].size(); i++)
		{
			if (dist[pat[node][i]] == dist[node] + 1 && cap[node][i]>0)
			{
				ind[pt] = i;
				blockflow(pat[node][i], len, go, pt + 1);
				if (gd < pt)break;
				else gd = INF;
			}
			idx[node]++;
		}
	}
	void dinic(int st, int go, int num)//dinicのアルゴリズムで最大流を求める 変数flowにmaxflowの値が入る
	{
		flow = 0;
		for (;;)
		{
			queue<pii>que;
			fill(dist, dist + num, INF);
			fill(flag, flag + num, false);
			que.push(make_pair(st, 0));
			for (;;)
			{
				if (que.empty())break;
				pii z = que.front();
				que.pop();
				if (flag[z.first])continue;
				flag[z.first] = true;
				dist[z.first] = z.second;
				for (int i = 0; i < pat[z.first].size(); i++)
				{
					if (dist[pat[z.first][i]]>z.second + 1 && cap[z.first][i] > 0)
					{
						dist[pat[z.first][i]] = z.second + 1;
						que.push(make_pair(pat[z.first][i], z.second + 1));
					}
				}
			}
			if (dist[go] == INF)return;
			gd = INF;
			fill(idx, idx + SIZE, 0);
			blockflow(st, dist[go], go, 0);
		}
	}
	vector<int>getcut(int st, int go, int num)//頂点iがmincutのst側なら1 そうでなければ0
	{
		dinic(st, go, num);
		vector<int>ret;
		for (int i = 0; i < num; i++)ret.push_back(flag[i]);
		return ret;
	}
};
maxflow fl;
class unionfind
{
public:
	int par[SIZE];
	int ran[SIZE];
	int ren[SIZE];
	void init()
	{
		for (int i = 0; i<SIZE; i++)
		{
			par[i] = i;
			ran[i] = 0;
			ren[i] = 1;
		}
	}
	int find(int a)
	{
		if (a == par[a])return a;
		else return par[a] = find(par[a]);
	}
	void unite(int a, int b)
	{
		a = find(a);
		b = find(b);
		if (a == b)return;
		if (ran[a]>ran[b])
		{
			par[b] = a;
			ren[a] += ren[b];
		}
		else
		{
			par[a] = b;
			ren[b] += ren[a];
		}
		if (ran[a] == ran[b])ran[b]++;
	}
};
unionfind uf;
int odeg[500], ideg[500];
bool flag[500];
void no()
{
	printf("NO\n");
	exit(0);
}
int main()
{
	int num, hei;
	scanf("%d%d", &num, &hei);
	uf.init();
	for (int i = 0; i < num; i++)
	{
		int za, zb, zc, zd;
		scanf("%d%d%d%d", &za, &zb, &zc, &zd);
		int s, t;
		if (zc == 0)s = za * 2;
		else s = zc * 2 + 1;
		if (zd == 0)t = zb * 2 + 1;
		else t = zd * 2;
		fl.adde(s, t, 1);
		uf.unite(s, t);
		odeg[s]++, ideg[t]++;
	}
	int sum = 0;
	for (int i = 1; i <= hei; i++)
	{
		if (odeg[i * 2] < ideg[i * 2])no();
		else if (odeg[i * 2] > ideg[i * 2])fl.adde(0, i * 2, odeg[i * 2] - ideg[i * 2]), sum += odeg[i * 2] - ideg[i * 2], flag[uf.find(i * 2)] = true;
		if (odeg[i * 2 + 1]>ideg[i * 2 + 1])no();
		else if (odeg[i * 2 + 1] < ideg[i * 2 + 1])fl.adde(i * 2 + 1, 1, ideg[i * 2 + 1] - odeg[i * 2 + 1]);
	}
	for (int i = 2; i <= hei * 2 + 1; i++)
	{
		if (i == uf.find(i))
		{
			if ((!flag[i]) && ideg[i] > 0)no();
		}
	}
	fl.dinic(0, 1, hei * 2 + 2);
	if (sum != fl.flow)no();
	printf("YES\n");
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:145:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &num, &hei);
                           ^
./Main.cpp:150:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &za, &zb, &zc, &zd);
                                        ^

Judge Result