結果

問題 No.241 出席番号(1)
ユーザー Kmcode1
提出日時 2015-07-10 22:38:53
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,949 bytes
コンパイル時間 1,243 ms
コンパイル使用メモリ 120,664 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 21:20:14
合計ジャッジ時間 2,400 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:161:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  161 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:163:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  163 |                 scanf("%d", &a[i]);
      |                 ~~~~~^~~~~~~~~~~~~

ソースコード

diff # 

#include<iostream>
#include<cstdio>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_map>
using namespace std;
class dinic{  //Dinic法
	/*
	max_frow(スタート,ゴール)　最大フローを求める
	dinic(int n)　頂点数
	add(from,go,容量)　辺の追加
	*/
public:
	struct ed{
		int cap;  //容量
		int rev;  //逆
		int to;  //行き先
	};
	vector<vector<ed> > g;  //頂点
	vector<int> level;  //startからの距離
	vector<int> iter;  //どこまで調べたか
	void bfs(int start){
		int kari = start;
		level.clear();
		level.assign(g.size(), -1);
		level[kari] = 0;
		queue<int> q;
		q.push(kari);
		while (!q.empty()){
			kari = q.front();
			q.pop();
			for (int i = 0; i<g[kari].size(); i++){
				if (g[kari][i].cap>0 && level[g[kari][i].to]<0){
					level[g[kari][i].to] = level[kari] + 1;
					q.push(g[kari][i].to);
				}
			}
		}
	}
	int dfs(int g1, int v66, int f66){  //現在地、目的地、frow
		if (g1 == v66){
			return f66;
		}
		/*いける場所をさがす*/
		for (int &i = iter[g1]; i<g[g1].size(); i++){
			if (level[g1]<level[g[g1][i].to] && g[g1][i].cap>0){
				int kari = 0;
				if (f66 == -1){
					kari = dfs(g[g1][i].to, v66, g[g1][i].cap);
				}
				else{
					kari = dfs(g[g1][i].to, v66, min(g[g1][i].cap, f66));
				}
				if (kari == -1){
					continue;
				}
				else{
					g[g1][i].cap -= kari;
					g[g[g1][i].to][g[g1][i].rev].cap += kari;
					return kari;
				}
			}
		}
		return -1;
	}
public:
	int max_frow(int s09, int t09){  //sからtへの最大フロー
		int re = 0;
		while (1){
			bfs(s09);
			if (level[t09] == -1){
				return re;
			}
			iter.clear();
			iter.assign(g.size(), 0);
			while (1){
				int ka = dfs(s09, t09, -1);
				if (ka == -1){
					break;
				}
				else{
					re += ka;
				}
			}
		}
	}
	void add(int ss21, int gg21, int cost21){  //ssからggにcost分加える
		ed kari;
		kari.to = gg21;
		kari.cap = cost21;
		kari.rev = g[gg21].size();
		g[ss21].push_back(kari);
		kari.cap = 0;
		kari.rev = g[ss21].size() - 1;
		kari.to = ss21;
		g[gg21].push_back(kari);
	}
	vector<int> mat;
	vector<bool> vis;
	bool b_dfs(int v){
		vis[v] = true;
		for (int i = 0; i < g[v].size(); i++){
			int go = g[v][i].to;
			int w = mat[go];
			if (w < 0 || (vis[w] == false && b_dfs(w))){
				mat[v] = go;
				mat[go] = v;
				return true;
			}
		}
		return false;
	}
	int bi(){
		int res = 0;
		vis.assign(g.size(), false);
		mat.assign(g.size(), -1);
		for (int i = 0; i < mat.size(); i++){
			if (mat[i] < 0){
				vis.assign(g.size(), false);
				if (b_dfs(i)){
					res++;
				}
			}
		}
		return res;
	}
	dinic(int n132){ //頂点数
		vector<ed> vgg;
		vgg.clear();
		g.assign(n132 + 5, vgg);
	}
};
int n;
int a[52];
dinic d(300);
vector<pair<int, int> > v;
int main(){
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	int base = 1;  //base+val
	int base2 = 52;  //base2+i
	int st = 0;
	int gol = 120;
	for (int i = 0; i < n; i++){
		d.add(st, base + i, 1);
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			if (a[j] == i){
				continue;
			}
			d.add(base + i, base2 + j, 1);
		}
	}
	for (int i = 0; i < n; i++){
		d.add(base2 + i, gol, 1);
	}
	int f = d.max_frow(st, gol);
	if (f != n){
		puts("-1");
		return 0;
	}
	for (int i = 0; i < n; i++){
		int ind = base + i;
		for (int j = 0; j < d.g[ind].size(); j++){
			if (d.g[ind][j].cap == 0){
				v.push_back(make_pair(d.g[ind][j].to - base2, i));
			}
		}
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++){
		printf("%d\n", v[i].second);
	}
	return 0;
}
0