头部背景图片
Decaku 's Blog |
Decaku 's Blog |

2018牛客国庆训练营 day6

C&H

签到。


G:

对方格染色,使得在所有操作后,每种颜色的sum都相同。


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
include<bits/stdc++.h>
using namespace std;
int a[1005][1005];
int color[1005][1005];
int n,ans,tem,sum;
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
scanf("%d",&a[i][j]);
color[i][j]=(i+j)%n;
if(a[i][j]==-1)
tem=color[i][j];
}
}
int _color,_sum=0;
if(tem==n-1) _color=n-2;
else _color=n-1;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(color[i][j]==_color)
_sum+=a[i][j];
if(color[i][j]==tem&&a[i][j]!=-1)
sum+=a[i][j];
}
}
printf("%d\n",_sum-sum);

}

A:

$拆点以后跑费用流,每个区域拆成n个点,一个蛋糕和第i层连边,其 \\费用是i*i-(i-1)*(i-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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int maxn=5005;
const int maxm=50005;
int s,t;
int num=-1,tot,sum;
int dis[maxn],b[maxn],xb[maxn],flow[maxn],fa[maxn];
int head[maxm];
struct Edge
{
int from,to,dis,nxt,w;
} edge[maxm*2];

void add_edge(int from,int to,int w,int dis)
{
edge[++num].nxt=head[from];
edge[num].from=from;
edge[num].to=to;
edge[num].w=w;
edge[num].dis=dis;
head[from]=num;
}
bool spfa()
{
for(int i=0; i<=maxn; i++)
dis[i]=inf;
memset(b,0,sizeof(b));
queue<int>que;
while(!que.empty()) que.pop();
memset(fa,-1,sizeof(fa));
b[s]=1;
dis[s]=0;
fa[s]=0;
flow[s]=inf;
que.push(s);
while(!que.empty())
{
int u=que.front();
que.pop();
b[u]=0;
for(int i=head[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].to;
if(edge[i].w>0&&dis[v]>dis[u]+edge[i].dis)
{
dis[v]=dis[u]+edge[i].dis;
fa[v]=u;
xb[v]=i;
flow[v]=min(flow[u],edge[i].w);
if(!b[v])
{
b[v]=1;
que.push(v);
}
}
}
}
return dis[t]<inf;
}

void max_flow()
{
while(spfa())
{
int k=t;
while(k!=s)
{
edge[xb[k]].w-=flow[t];
edge[xb[k]^1].w+=flow[t];
k=fa[k];
}
tot+=flow[t];
sum+=flow[t]*dis[t];
}
}

int main()
{
memset(head,-1,sizeof(head));
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++)
{
int a,b;
cin>>a>>b;
for(int j=1; j<=n; j++)
{
add_edge(i,n+(j-1)*m+a,1,2*j-1);
add_edge(n+(j-1)*m+a,i,0,1-2*j);
add_edge(i,n+(j-1)*m+b,1,2*j-1);
add_edge(n+(j-1)*m+b,i,0,1-2*j);
}
}
for(int i=1; i<=n; i++)
{
add_edge(0,i,1,0);
add_edge(i,0,0,0);
}
for(int i=n+1; i<=n+n*m; i++)
{
add_edge(i,n+n*m+1,1,0);
add_edge(n+n*m+1,i,0,0);
}
s=0;
t=n+n*m+1;
max_flow();
cout<<sum<<endl;
}
avatar Decaku 菜菜菜