Submission #11329794

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXN = 105;
const int MAXM = 105;

/*wtf*/
bool chk[MAXN * MAXN];
struct bpm{
	vector<int> gph[MAXN];
	int dis[MAXN], l[MAXN], r[MAXM], vis[MAXN];
	void clear(){ for(int i=0; i<MAXN; i++) gph[i].clear();	}
	void add_edge(int l, int r){ gph[l].push_back(r); }
	bool bfs(int n){
		queue<int> que;
		bool ok = 0;
		memset(dis, 0, sizeof(dis));
		for(int i=0; i<n; i++){
			if(l[i] == -1 && !dis[i]){
				que.push(i);
				dis[i] = 1;
			}
		}
		while(!que.empty()){
			int x = que.front();
			que.pop();
			for(auto &i : gph[x]){
				if(r[i] == -1) ok = 1;
				else if(!dis[r[i]]){
					dis[r[i]] = dis[x] + 1;
					que.push(r[i]);
				}
			}
		}
		return ok;
	}
	bool dfs(int x){
		if(vis[x]) return 0;
		vis[x] = 1;
		for(auto &i : gph[x]){
			if(r[i] == -1 || (!vis[r[i]] && dis[r[i]] == dis[x] + 1 && dfs(r[i]))){
				l[x] = i; r[i] = x;
				return 1;
			}
		}
		return 0;
	}
	int match(int n){
		memset(l, -1, sizeof(l));
		memset(r, -1, sizeof(r));
		int ret = 0;
		while(bfs(n)){
			memset(vis, 0, sizeof(vis));
			for(int i=0; i<n; i++) if(l[i] == -1 && dfs(i)) ret++;
		}
		return ret;
	}
	bool chk[MAXN + MAXM];
	void rdfs(int x, int n){
		if(chk[x]) return;
		chk[x] = 1;
		for(auto &i : gph[x]){
			chk[i + n] = 1;
			rdfs(r[i], n);
		}
	}
	vector<int> getcover(int n, int m){ // solve min. vertex cover
		match(n);
		memset(chk, 0, sizeof(chk));
		for(int i=0; i<n; i++) if(l[i] == -1) rdfs(i, n);
		vector<int> v;
		for(int i=0; i<n; i++) if(!chk[i]) v.push_back(i);
		for(int i=n; i<n+m; i++) if(chk[i]) v.push_back(i);
		return v;
	}
}bpm;

int n, m, a[MAXN][MAXN], b[MAXN][MAXN];
int X[MAXN][MAXN];

int main(){
	auto print_grid = [&](int v[MAXN][MAXN]){
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				printf("%d ", v[i][j]);
			}
			puts("");
		}
	};
	scanf("%d %d",&n,&m);
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=0; i<m; i++){
		memset(X, 0, sizeof(X));
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				if(chk[a[i][j]]) continue;
				int col = (a[i][j] - 1) / m;
				X[i][col] = a[i][j];
			}
		}
		bpm.clear();
		for(int i=0; i<n; i++) for(int j=0; j<n; j++){
			if(X[i][j]) bpm.add_edge(i, j);
		}
		assert(bpm.match(n) == n);
		for(int j=0; j<n; j++){
			b[j][i] = X[j][bpm.l[j]];
			chk[b[j][i]] = 1;
		}
	}
	print_grid(b);
	for(int i=0; i<m; i++){
		vector<int> v;
		for(int j=0; j<n; j++) v.push_back(b[j][i]);
		sort(all(v));
		for(int j=0; j<n; j++) b[j][i] = v[j];
	}
	print_grid(b);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:93:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
./Main.cpp:96:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a[i][j]);
                        ^

Judge Result