2021牛客暑期多校训练营3
2021牛客暑期多校训练营3
B Black and white
对于一个位置\((i,j)\)，选择这个位置的数就给\(（out_i,in_j）\)连一条边，考虑四个点\((i,j)(i,k)(l,j)(l,k)\)被涂成黑色对应了\(out_i out_l\)和\(in_i in_l\)构成的一个四元环。其中一个点自动涂黑就是四元环断一条边，即这四个点刚好连通。
类似的，全部位置涂黑其实就是求图中的一棵生成树。
所以用prim\(O(n^2)\)求最小生成树即可。
#include
#include
#include
#include
#include
using namespace std;
#define LL long long
#define INF 2147483647
#define N 5050
int read(){
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return sum*f;
}
int e[N*2][N*2];
int dis[N*2];
bool vis[N*2];
signed main(){
int n=read(),m=read();
LL a=read(),b=read(),c=read(),d=read(),p=read();
for(int i=1;i<=n+m;i++)
for(int j=1;j<=m+n;j++)
e[i][j]=INF;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
a=(a*a%p*b%p+a*c%p+d)%p;
e[i][j+n]=e[j+n][i]=a;
}
for(int i=1;i<=n+m;i++)dis[i]=INF;
dis[1]=0;
LL ans=0;
for(int i=1;i<=n+m;i++){
int u,tmp=INF;
for(int j=1;j<=n+m;j++)
if(vis[j]==0&&dis[j] C Minimum grid
考虑最大的\(C_j\)和\(B_i\)
填数时只能选择满足条件的行和列并的若干个格子。
一个格子\((i,j)\)中可以填数代表选择了从\(out_i\)到\(in_j\)的一条边。
其实就是二分图的最小边覆盖。
最小边覆盖=总点数-最大匹配
求最大匹配即可。
之后求次大的\(C_j\)和\(B_i\)直到满足所有条件为止。
那么证明若干个最小边覆盖（就是最优的选点方案）没有冲突呢？
发现可以使答案变优的解在满足条件的行和列的交上。
这些交不能在考虑其他\(C_j\)和\(B_i\)时填数，不能使答案更优就随便填，我们不关心具体位置。因为题目保证了至少有一种可行方案，所以不用考虑。
#include
#include
#include
#include
#include
using namespace std;
const int N=2111;
int cnt,head[N*2],match[N*2],id_n[N],id_m[N];
bool vis[N*2],E[N][N];
struct edge{
int to,nxt;
}e[N*N];
struct limit{
int id,type,w;
}c[N*2];
bool cmp(limit a,limit b){
return a.w>b.w;
}
void add_edge(int u,int v){
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
int read(){
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return sum*f;
}
bool dfs(int u){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v])continue;
vis[v]=1;
if(!match[v]||dfs(match[v])){
match[v]=u;
return true;
}
}
return false;
}
int main(){
int n=read(),m=read(),k=read();
for(int i=1;i<=n;i++)
c[i].type=1,c[i].w=read(),c[i].id=i;
for(int i=1;i<=n;i++)
c[i+n].type=2,c[i+n].w=read(),c[i+n].id=i;
for(int i=1;i<=m;i++)E[read()][read()]=1;
sort(c+1,c+1+2*n,cmp);
int now=1;
int ans=0;
int num_n=0,num_m=0;
while(now<=n*2+1){
if(c[now].w!=c[now-1].w){
cnt=0;
memset(head,0,sizeof(head));
for(int i=1;i<=num_n;i++)
for(int j=1;j<=num_m;j++){
if(E[id_n[i]][id_m[j]]==0)continue;
add_edge(id_n[i],id_m[j]+n);
add_edge(id_m[j]+n,id_n[i]);
}
memset(match,0,sizeof(match));
int tmp=0;
for(int i=1;i<=num_n;i++){
memset(vis,0,sizeof(vis));
tmp+=dfs(id_n[i]);
}
ans+=(num_n+num_m-tmp)*c[now-1].w;
num_n=num_m=0;
}
if(c[now].type==1)id_n[++num_n]=c[now].id;
if(c[now].type==2)id_m[++num_m]=c[now].id;
now++;
}
printf("%d",ans);
return 0;
}
F 24dian
爆搜，心态爆炸，做题之前一定要确定题目的意思。
#include
#include
#include
#include
#include
#include