欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[Wc2007]剪刀石头布 迭代

程序员文章站 2022-05-20 21:41:46
...

Description
给你若干条边,你自己安排剩下的边,求最多有多少个三元环。


Sample Input
3
0 1 2
0 0 2
2 2 0


Sample Output
1
0 1 0
0 0 1
1 0 0


首先可能的三元环数量为:C(n,3)C(n,3)
考虑一个非法的三元环就相当于有一个点有两个出度,那么答案就是:
ans=C(n,3)i=1nC(degi,2)ans=C(n,3)-\sum_{i=1}^nC(degi,2)
这个东西你是可以直接费用流的吗。
但是Discuss又有一种做法,我去了解了一下:
就是你先给他们随机安排一个值,然后你期望让所有人的degdeg尽量相近,就相当于让一些人的degdeg变小,一些人的degdeg变大,Discuss是说只要找到当前的degdeg差距大于等于22,就直接修改。正确性不会证,比较显然???时间复杂度,我的姿势不好可能会很慢,其实一次增广路可以做到O(m)O(m),复杂度应该是O(m2)O(m^2)的。
我这个算法比我写的费用流快很多。。。


#include <ctime>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;
typedef long long LL;
int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
const int N = 101;
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}
void put(int x) {
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

struct node {
	int x, y;
} b[N * N]; int cnt;
struct edge {
	int x, y, next;
} e[N * N * 2]; int len, last[N];
int ans, a[N][N], id[N * N];
int tt, v[N];
int du[N];

void ins(int x, int y) {
	e[++len].x = x, e[len].y = y;
	e[len].next = last[x], last[x] = len;
}

bool cmp(int x, int y) {return du[x] > du[y];}

bool findrd(int x, int d) {
	v[x] = tt;
	for(int k = last[x]; k; k = e[k].next) {
		int y = e[k].y;
		if(v[y] != tt && a[x][y]) {
			if(d - du[y] >= 2) {
				a[x][y] = 0, a[y][x] = 1;
				ans -= du[y], du[y]++;
				return 1;
			} else if(findrd(y, d)){
				a[x][y] = 0, a[y][x] = 1;
				return 1;
			}
		}
	} return 0;
}

int main() {
	srand(200815147);
	int n = read();
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			a[i][j] = read();
			if(i <= j) continue;
			if(a[i][j] == 0) ++du[j];
			else if(a[i][j] == 1) ++du[i];
			else {
				ins(i, j), ins(j, i);
				b[++cnt].x = i, b[cnt].y = j;
			}
		}
	} 
	for(int i = 1; i <= cnt; i++) id[i] = i;
	random_shuffle(id + 1, id + cnt + 1);
	for(int i = 1; i <= cnt; i++) {
		int hh = id[i];
		if(du[b[hh].x] <= du[b[hh].y]) ++du[b[hh].x], a[b[hh].x][b[hh].y] = 1, a[b[hh].y][b[hh].x] = 0;
		else ++du[b[hh].y], a[b[hh].x][b[hh].y] = 0, a[b[hh].y][b[hh].x] = 1;
	} 
	ans = n * (n - 1) / 2 * (n - 2) / 3;
	for(int i = 1; i <= n; i++) ans -= du[i] * (du[i] - 1) / 2;
	bool bk = 1;
	while(bk) {
		bk = 0;
		for(int i = 1; i <= n; i++) id[i] = i;
		sort(id + 1, id + n + 1, cmp);
		for(int i = 1; i <= n; i++) {
			tt++; int x = id[i];
			if(findrd(x, du[x])) {
				du[x]--, ans += du[x];
				bk = 1; break;
			}
		}
	} put(ans), puts("");
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) put(a[i][j]), putchar(' ');
		puts("");
	}
	return 0;
}

相关标签: 迭代