【WC2007】剪刀石头布

Source and Judge

WC2007
bzoj2957

Analysis

请先思考后再展开

hello everyone
i am zory
first i will ak noi 2019
then i will ak ioi 2020
hope everyone can mobai me
这道题感觉最难的就是,给你一个图你怎么计数
首先肯定是贡献到点上面,如果直接对三元环考虑,对于x考虑i和j,那么会跟i和j之间的边有关,很麻烦
但补集转化,非三元环的话,一定是从某个点出发,第三条边随意,这样就很好处理了,而且只会被统计一次
所以就是 $\sum C(deg_i,2)$
那么费用流,增量法建图即可,这个和【CQOI2014】学习小组挺像的

我写得常数很大……

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmin(ll &x,ll y) {x=x<y?x:y;}
const int MAX_N=110;
int hou[MAX_N*MAX_N*3];
struct Edge{int y,c,w,g;}e[MAX_N*MAX_N*4*2*2];
int ln=0;int oth(int x) {return x&1?x+1:x-1;}
void ins(int x,int y,int c,int w)
{
e[++ln]=(Edge){y,c,w,hou[x]};hou[x]=ln;
e[++ln]=(Edge){x,0,-w,hou[y]};hou[y]=ln;
}
int st,ed;
int dis[MAX_N*MAX_N*3],fm[MAX_N*MAX_N*3],mif[MAX_N*MAX_N*3];bool v[MAX_N*MAX_N*3];
int cost=0;
queue<int> q;
bool solve()
{
memset(dis,0x3f,sizeof dis);
q.push(st);dis[st]=0;mif[st]=INF;v[st]=1;
while(q.size())
{
int x=q.front();q.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(dis[y]>dis[x]+e[k].w and e[k].c)
{
dis[y]=dis[x]+e[k].w;
fm[y]=k;mif[y]=min(mif[x],e[k].c);
if(!v[y]) v[y]=1,q.push(y);
}
v[x]=0;
}
}
if(dis[ed]==INF) return 0;
cost+=dis[ed]*mif[ed];
for(int x=ed;x!=st;x=e[oth(fm[x])].y) e[fm[x]].c-=mif[ed],e[oth(fm[x])].c+=mif[ed];
return 1;
}
int n;pr out[MAX_N*MAX_N*2];
inline int calc(int x,int y) {return min(x,y)*(n+1)+max(x,y);}
int ans[MAX_N][MAX_N];
void main()
{
scanf("%d",&n);int m=n*n*2;st=0,ed=m+n+1;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) out[calc(i,j)]=MP(i,j);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ins(m+i,ed,1,j-1);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
{
int t=qread();
if(i<j)
{
if(t==2) ins(st,calc(i,j),1,0),ins(calc(i,j),m+i,1,0),ins(calc(i,j),m+j,1,0);
else ins(st,m+(t==1?j:i),1,0);
}
ans[i][j]=t;
}
while(solve()) ;
printf("%d\n",n*(n-1)/2*(n-2)/3-cost);
for(int k=hou[st];k>0;k=e[k].g)
{
int y=e[k].y;if(y>m) continue;
for(int k2=hou[y];k2>0;k2=e[k2].g) if(e[k2].c==0 and e[k2].y!=st)
{
int a=e[k2].y-m,b=(a==out[y].FR?out[y].SE:out[y].FR);
ans[b][a]=1;ans[a][b]=0;
}
}
for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("%d ",ans[i][j]);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/72cc.html
转载请注明出处,谢谢!