调整很优的情形：
调整严格不变劣
要能尽量多调
如果调不下去，可以找到两个颜色构成的连通块，把这个连通块颜色反转
有一张无向图，她想对顶点3染色，满足相同颜色顶点之间没有连边。给出一个方案
- 给每个点随机赋三种颜⾊之⼀
- 将所有点扫⼀遍。扫到 号点时，考虑固定其他节点颜⾊调整 号点颜⾊，使得同⾊边数最少。如有
多种选择，可随机⼀个。 - 重复步骤2，直到没有同⾊边。 容易发现，同⾊边数是不减的。⽽严格不变劣、可⼀直进⾏的调整
对许多题⽬都很优秀。
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=2e5+10;
vector<int>E[MAXN];
int col[MAXN],n,m,cnt[4],a[MAXN],b[MAXN];
main(){
srand(time(0));
n=read();m=read();
fp(i,1,m){
a[i]=read();b[i]=read();
E[a[i]].push_back(b[i]);E[b[i]].push_back(a[i]);
}
fp(i,1,n)col[i]=rand()%3+1;
while(1){
fp(i,1,n){
mem(cnt);
for(int x:E[i])++cnt[col[x]];
int mn=1e9,p;
fp(j,1,3)if(cnt[j]<mn||(cnt[j]==mn&&(rand()&1)))p=j,mn=cnt[j];
col[i]=p;
}
fp(i,1,m)if(col[a[i]]==col[b[i]])goto ss;
fp(i,1,n)printf("%d ",col[i]);puts("");return 0;
ss:;
}
}
「JOISC 2020 Day4」传奇团子师傅
别人说的最少60分的算法我就能实现成49分 弱到了极致 而且写了半天
如果有可以串但没串的 串上
否则 有串了之后只和一个矛盾的 以一半概率串上并替代原来的
我调整100次和10000次没有差别
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=2010;
const int fx[]={-1,-1,0,1},fy[]={0,1,1,1};
char mp[MAXN][MAXN];
int id[MAXN][MAXN],n,m,cnt,book[MAXN][MAXN];
pair<int,int>buc[MAXN*MAXN];
inline void mark(int x,int y,int j){
int x1=x-fx[j],y1=y-fy[j],x2=x+fx[j],y2=y+fy[j];
book[x1][y1]=book[x2][y2]=id[x][y];book[x][y]=j;
}
inline void unmark(int p){
int x=buc[p].first,y=buc[p].second;int j=book[x][y];if(j==-1)return;
int x1=x-fx[j],y1=y-fy[j],x2=x+fx[j],y2=y+fy[j];
book[x1][y1]=book[x2][y2]=0;book[x][y]=-1;
}
inline bool check(int x,int y){return x>0&&y>0&&x<=n&&y<=m;}
mt19937 gen(20020328);
main(){
//freopen("input_05.txt","r",stdin);freopen("output_05.txt","w",stdout);
n=read();m=read();
fp(i,1,n){
scanf("%s",mp[i]+1);
fp(j,1,m)if(mp[i][j]=='W')id[i][j]=++cnt,book[i][j]=-1,buc[cnt]={i,j};
}
fp(tt,1,100){
fp(i,1,cnt){
int x=buc[i].first,y=buc[i].second;
fp(j,0,3){
int x1=x-fx[j],y1=y-fy[j],x2=x+fx[j],y2=y+fy[j];
if(!check(x1,y1)||!check(x2,y2))continue;
if(mp[x1][y1]=='W'||mp[x2][y2]=='W'||mp[x1][y1]==mp[x2][y2])continue;
if(!book[x1][y1]&&!book[x2][y2]){unmark(id[x][y]),mark(x,y,j);break;}//这里原先判了个如果已经匹配上了 以一半概率匹配新的 但加完了反而不优
else if(!book[x1][y1]&&book[x][y]==-1)if(gen()&1){unmark(book[x2][y2]);mark(x,y,j);}
else if(!book[x2][y2]&&book[x][y]==-1)if(gen()&1){unmark(book[x1][y1]);mark(x,y,j);}
}
}
}
fp(i,1,n){
fp(j,1,m){
if(mp[i][j]=='W'){
int t=book[i][j];
if(t==-1)putchar('W');
else if(t==0)putchar('|');
else if(t==1)putchar('/');
else if(t==2)putchar('-');
else putchar('\');
}
else putchar(mp[i][j]);
}
putchar('
');
}
return 0;
}
给出一张m个点n条边的简单图，要求构造一组用4种颜色给所有点染色的方案，使
得每个点最多与一个与其同色的点相邻。
保证每个点的度数不大于(7)。
首先让每个点随机染色
考虑一个点(x)，如果它相邻的点有至少两个和它颜色相同，则我们至少能找到一种颜
色(c)，使得它相邻的点中颜色c出现不超过1次 (
ightarrow) 把(x)的颜色改成(c)
代码不是我写的。。
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
int main()
{
int n, m;
scanf("%d%d", &m, &n);
vvi g(n + 1);
for (int i = 1; i <= m; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
vi a(n + 1);
vector<bool> inq(n + 1);
queue<int> q;
for (int i = 1; i <= n; ++i)
{
inq[i] = true;
q.push(i);
}
while (!q.empty())
{
int u = q.front();
inq[u] = false;
q.pop();
vi cnt(4);
for (auto v : g[u]) ++cnt[a[v]];
if (cnt[a[u]] >= 2)
{
for (int i = 0; i < 4; ++i)
{
if (cnt[i] <= 1)
{
a[u] = i;
break;
}
}
for (auto v : g[u])
{
if (!inq[v])
{
inq[v] = true;
q.push(v);
}
}
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= 4; ++j)
{
if (j != a[i] + 1)
{
printf("%d ", j);
}
}
puts("");
}
return 0;
}