백준1960 행렬만들기

작성일 | In

문제 링크

  • http://icpc.me/1960

사용 알고리즘

  • 네트워크 플로우
  • 최대 유량

풀이

왼쪽에는 각 행을 대표하는 정점을 두고, 오른쪽에는 각 열을 대표하는 정점을 둡니다.
그리고 소스(S)는 왼쪽 정점과, 싱크(T)는 오른쪽 정점과 연결해줍니다. 각 간선의 capacity는 행/열의 합으로 잡아줍니다.
그런 다음 행을 대표하는 정점들과 열을 대표하는 정점들이 모두 연결되어있는 완전 그래프를 만들어주고, 이때 간선의 capacity는 1로 해줍니다.

위 사진처럼 만든 그래프에서 max flow를 흘려준 뒤, i행과 j열을 잇는 간선에 유량이 흐르고 있다면 (i, j)칸에 1을 넣어주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;

int c[1010][1010];
int f[1010][1010];
int bias = 500;
int n;
int s = 1001, t = 1002;
vector<int> g[1010];

int arr[555][555];

vector<int> a, b;

void addEdge(int s, int e, int x = 1){
	g[s].push_back(e); c[s][e] = x;
	g[e].push_back(s);
}

bool chk(){
	for(int i=1; i<=n; i++){
		int sum = 0;
		for(int j=1; j<=n; j++) sum += arr[i][j];
		if(sum != a[i]) return 0;
	}

	for(int j=1; j<=n; j++){
		int sum = 0;
		for(int i=1; i<=n; i++) sum += arr[i][j];
		if(sum != b[j]) return 0;
	}

	return 1;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; a.resize(n+1); b.resize(n+1);
	for(int i=1; i<=n; i++){
		int x; cin >> x;
		addEdge(s, i, x);
		a[i] = x;
	}
	for(int i=bias+1; i<=bias+n; i++){
		int x; cin >> x;
		addEdge(i, t, x);
		b[i-bias] = x;
	}
	for(int i=1; i<=n; i++){
		for(int j=bias+1; j<=bias+n; j++){
			addEdge(i, j);
		}
	}

	int par[1010];
	while(1){
		int mx = 1e9+7;
		memset(par, -1, sizeof par);
		queue<int> q; q.push(s);
		while(q.size()){
			int now = q.front(); q.pop();
			for(auto nxt : g[now]){
				if(par[nxt] == -1 && c[now][nxt] - f[now][nxt] > 0){
					par[nxt] = now; q.push(nxt);
				}
			}
		}
		if(par[t] == -1) break;
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			mx = min(mx, c[a][b] - f[a][b]);
		}
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			f[a][b] += mx; f[b][a] -= mx;
		}
	}

	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(f[i][j+bias]) arr[i][j] = 1;
		}
	}

	if(!chk()) cout << -1;
	else{
		cout << 1 << "\n";
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				cout << arr[i][j];
			}
			cout << "\n";
		}
	}
}