https://lydsy.com/JudgeOnline/problem.php?id=3935

分析:

  • 如果知道更改后的状态,那么代价和是否合法都能求出来
  • 对不合法的情况也设一个估价函数。
  • 随机这个01串,模拟退火即可。

    (已更新正解)

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
#define N 550
typedef long long ll;
#define inf 0x3f3f3f3f
typedef double f2;
f2 Rand() {
return f2(rand())/RAND_MAX;
}
int head[N],to[N<<1],nxt[N<<1],n,cnt,w[N],X,val[N<<1];
ll dis[N][N];
int len[N],vec[N][N];
inline void add(int u,int v,int w) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
void dfs(int x,int y,int rt) {
int i;
for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {
dis[rt][to[i]]=dis[rt][x]+val[i];
dfs(to[i],x,rt);
}
}
struct A {
int a[N],ans;
A() {ans=inf;}
}ANS,TMP;
int check(const A &x) {
int i,j,re=0;
for(i=1;i<=n;i++) if(x.a[i]==0) {
int flg=0;
for(j=1;j<=len[i];j++) if(x.a[vec[i][j]]) {
flg=1; break;
}
if(!flg) re++;
}
return re;
}
void calc(A &x) {
int i,t=0;
for(i=1;i<=n;i++) t+=(x.a[i]!=w[i]);
int tmp=check(x);
if(tmp) x.ans=tmp*2+(n>>1);
else x.ans=(t>>1);
if(x.ans<ANS.ans) ANS=x;
}
int t0[N],t1[N],l1,l0;
A kuo(const A &x,int y) {
A re=x;
int i; for(i=1;i<=y;i++) {
int l=rand()%l1+1,r=rand()%l0+1;
swap(re.a[t1[l]],re.a[t0[r]]);
}
return re;
}
void orztuihuo(f2 BG,f2 ED,f2 d) {
calc(TMP);
A now=TMP;
l0=l1=0;
int i;
for(i=1;i<=n;i++) {
if(!now.a[i]) t0[++l0]=i;
else t1[++l1]=i;
}
for(;BG>ED;BG*=d) {
A nxt=kuo(now,max(1.0,BG));
calc(nxt);
if(nxt.ans < now.ans || Rand() < exp((now.ans-nxt.ans)/BG)) {
now=nxt;
l0=l1=0;
for(i=1;i<=n;i++) {
if(!now.a[i]) t0[++l0]=i;
else t1[++l1]=i;
}
}
}
for(i=1;i<=10000;i++) {
A nxt=kuo(ANS,1);
calc(nxt);
}
}
int main() {
srand(114514); rand();
scanf("%d%d",&n,&X);
int i,j;
for(i=1;i<=n;i++) scanf("%d",&w[i]);
int x,y,z;
for(i=1;i<n;i++) {
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
for(i=1;i<=n;i++) dfs(i,0,i);
for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j&&dis[i][j]<=X) {
vec[i][++len[i]]=j;
}
ANS.ans=inf;
int sw=0;
for(i=1;i<=n;i++) TMP.a[i]=w[i],sw+=w[i];
random_shuffle(TMP.a+1,TMP.a+n+1); if(n<=100) orztuihuo(50,0.001,0.999);
else if(sw>100) orztuihuo(100,0.1,0.999998);
else orztuihuo(100,0.01,0.99993);
// for(i=1;i<=n;i++) printf("%d ",ANS.a[i]); puts("");
printf("%d\n",ANS.ans>n?-1:ANS.ans);
}

正解:

我的做法是设\(i\)节点\(x_i\)表示是否被交换过。

那么如果原来是\(0\),现在就是\(x_i\),原来是1,现在就是\(1-x_i\)。

列出几个限制然后单纯形法水过

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef double f2;
#define N 515
#define eps 1e-8
int head[N],to[N<<1],nxt[N<<1],val[N<<1],n,cnt,wa[N];
ll dis[N][N],X;
f2 a[N<<1][N];
inline void add(int u,int v,int w) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
void dfs(int x,int y,int rt,ll d) {
dis[rt][x]=d;
int i;
for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {
dfs(to[i],x,rt,d+val[i]);
}
}
void pivot(int r,int c,int n,int m) {
int i,j;
f2 t=-a[r][c]; a[r][c]=-1;
for(i=0;i<=n;i++) a[r][i]/=t;
for(i=0;i<=m;i++) if(abs(a[i][c])>eps&&i!=r) {
t=a[i][c]; a[i][c]=0;
for(j=0;j<=n;j++) a[i][j]+=t*a[r][j];
}
}
void simplex(int n,int m) {
int i,j,k;
f2 t;
while(1) {
i=j=0;
t=-eps;
for(k=1;k<=m;k++) if(a[k][0]<t) t=a[i=k][0];
if(!i) break;
for(k=1;k<=n;k++) if(a[i][k]>eps) {
j=k; break;
}
if(!j) {puts("-1"); return ;}
pivot(i,j,n,m);
}
while(1) {
i=j=0;
t=eps;
for(k=1;k<=n;k++) if(a[0][k]>t) t=a[0][j=k];
if(!j) break;
t=1e9;
for(k=1;k<=m;k++) if(a[k][j]<-eps&&(-a[k][0]/a[k][j])<t) {
t=-a[k][0]/a[k][j]; i=k;
}
if(!i) {puts("INF"); return ;}
pivot(i,j,n,m);
}
if(abs(a[0][0])<eps) puts("0");
else if(-a[0][0]>n) puts("-1");
else printf("%.0f\n",-a[0][0]/2);
}
int main() {
scanf("%d%lld",&n,&X);
int i,x,y,z,j,sum=0;
for(i=1;i<=n;i++) scanf("%d",&wa[i]),sum+=wa[i];
for(i=1;i<n;i++) {
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
for(i=1;i<=n;i++) {
dfs(i,0,i,0);
}
for(i=1;i<=n;i++) a[0][i]=-1;
for(i=1;i<=n;i++) {
int t=0;
for(j=1;j<=n;j++) {
if(dis[i][j]<=X) {
if(wa[j]) t++,a[i][j]=-1;
else a[i][j]=1;
}
}
a[i][0]=t-1;
}
int t=0;
for(i=1;i<=n;i++) {
if(wa[i]) t++,a[n+1][i]=-1;
else a[n+1][i]=1;
}
a[n+1][0]=t-sum;
t=0;
for(i=1;i<=n;i++) {
if(wa[i]) t--,a[n+2][i]=1;
else a[n+2][i]=-1;
}
a[n+2][0]=t+sum;
int tot=n+2;
for(i=1;i<=n;i++) {
a[++tot][i]=-1;
a[tot][0]=1;
}
simplex(n,tot);
}

最新文章

  1. 使用 Composer 为 ThinkPHP(3.2.3)框架添加和管理组件
  2. 【学习笔记】在原生javascript中使用ActiveX和插件
  3. 探秘Tomcat(一)——Myeclipse中导入Tomcat源码
  4. linux下安装+配置+卸载jdk
  5. Oracle Rac crs无法启动
  6. Eclipse中安装可以新建html文件的插件(Eclipse HTML Editor)
  7. MongoDB存储时间
  8. Qt中QFtp获取带有中文的文件名称出现乱码的解决方法(执行操作前就转换编码)
  9. 基础总结篇之五:BroadcastReceiver应用具体解释
  10. C# 语言规范_版本5.0 (第10章 类)
  11. kindeditor上传图片时候,上传成功了,但是页面上却提示失败
  12. chrome开发工具指南(五)
  13. python 从视频中提取图片,并保存在硬盘上
  14. 【一天一道LeetCode】#344. Reverse String
  15. Android 取消标题栏
  16. shell提取文件后缀名,并判断其是否为特定字符串
  17. 思科交换机根据mac地址限制主机
  18. nginx location配置和rewrite写法
  19. 梯度消失(vanishing gradient)与梯度爆炸(exploding gradient)问题
  20. Java Web(十一) 分页功能的实现

热门文章

  1. 高性能HTTP加速器Varnish安装与配置(包含常见错误)
  2. 本地filezilla&amp;amp;servervsftp搭配使用
  3. 网页图表类框架(插件)——百度eCharts和Highcharts
  4. Python 时间格式化(转)
  5. jquery实现重置
  6. UITableView使用指南
  7. async &amp; await (转载)
  8. 九度OJ 1158:买房子 (基础题)
  9. 九度OJ 1053:互换最大最小数 (基础题)
  10. 九度OJ 1013:开门人和关门人 (排序)