模拟退火做法求助

love_yyc @ 2022-10-26 09:02:14

by viopark @ 2022-11-04 18:50:06

@creation_hy 优雅，实在是太优雅了

by Harry_W @ 2022-11-06 15:12:30

这种题有必要吗???

by Gunpowder_OI @ 2022-11-25 21:15:36

看到大家都在发我也来水一波树状数组

#include <bits/stdc++.h>
using namespace std;
int n, a, c[110];
int lowbit (int x){return x & (-x);}
void update (int x, int k){
    for (int i = x; i <= n; i += lowbit (i))c[i] += k;
}
int getsum (int x){
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit (i))ans += c[i];
    return ans;
}
int main (){
    n = 2;
    for (int i = 1; i <= n; i++)cin >> a, update (i, a);
    cout << getsum (n);
    return 0;
}

by x383494 @ 2023-06-09 11:56:01

看到大家都在发我也来水一波最大流

建源 S，汇 T，S,T 间连容量为 a,b 的两条边，最大流即为 a+b。

#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#define UP(i,s,e) for(auto i=s; i!=e; ++i)
#define sd std::
namespace flow{ // }{{{
using typ = int;
constexpr int V = 2, E = 2;
int iv, is, it;
struct Edge{int to, nxt, lf;} es[E*2+2];
constexpr int EDGE_NIL = 0;
constexpr int INF = 0x3f3f3f3f;
int h[V]; typ ex[V];
int head[V], gap[V+1];
sd stack<int> hnods[V];
int maxh = 0, cnt = 2;
void init(int v, int s, int t){
    iv=v, is=s, it=t;
    memset(gap, 0, sizeof gap);
    memset(head, 0, sizeof head);
    memset(ex, 0, sizeof ex);
    maxh = 0, cnt = 2;
}
void addflow(int s, int t, int c){
    es[cnt] = {t, head[s], c}, head[s] = cnt++;
    es[cnt] = {s, head[t], 0}, head[t] = cnt++;
}
void push(int x){
    for(int i=head[x]; i!=EDGE_NIL; i=es[i].nxt){
        if(x!=is && ex[x] == 0) break;
        int t = es[i].to, w = es[i].lf;
        if(!w || h[t] > h[x]) continue;
        if(x==is || h[t] == h[x]-1){
            int df = x==is ? w : (int)sd min(ex[x], (typ)w);
            ex[x]-=df;
            es[i].lf-=df, es[i^1].lf+=df;
            if(ex[t] == 0 && t != it && t != is){
                hnods[h[t]].push(t);
                maxh = sd max(maxh, h[t]);
            }
            ex[t] += df;
        }
    }
}
void relabel(int x){
    h[x] = iv;
    for(int i=head[x]; i!=EDGE_NIL; i=es[i].nxt){
        if(es[i].lf) h[x] = sd min(h[x], h[es[i].to]);
    }
    if(++h[x] < iv){
        hnods[h[x]].push(x);
        maxh = sd max(maxh, h[x]);
        ++gap[h[x]];
    }
}
int gethiest(){
    while(hnods[maxh].empty() && maxh >= 0) maxh--;
    if(maxh == -1) return -1;
    int ret = hnods[maxh].top();
    hnods[maxh].pop();
    return ret;
}
void bfs_init(){
    memset(h, 0x3f, sizeof h);
    h[it] = 0;
    sd queue<int> todo;
    todo.push(it);
    while(!todo.empty()){
        int s = todo.front();
        todo.pop();
        for(int i=head[s]; i!=EDGE_NIL; i=es[i].nxt){
            int t=es[i].to;
            if(es[i^1].lf && h[t]>h[s]+1){
                h[t] = h[s]+1;
                todo.push(t);
            }
        }
    }
}
void hlpp(){
    bfs_init();
    if(h[is] == INF) return;
    h[is] = iv;
    UP(i, 0, iv) if(h[i]!=INF) gap[h[i]]++;
    push(is);
    int x;
    while((x=gethiest())!=-1){
        push(x);
        if(ex[x]){
            if(!--gap[h[x]]){
                UP(i, 0, iv){
                    if(i==is || i==it) continue;
                    if(h[i]>h[x] && h[i]<iv+1) h[i] = iv+1; 
                }
            }
            relabel(x);
        }
    }
}
} // {}}}
namespace m{ // }{{{
int ia, ib;
void work(){
    scanf("%d%d", &ia, &ib);
    flow::init(2, 0, 1);
    flow::addflow(0, 1, ia);
    flow::addflow(0, 1, ib);
    flow::hlpp();
    printf("%d\n", flow::ex[1]);
}
} // {}}}
int main(){m::work(); return 0;}

by x383494 @ 2023-06-09 12:02:46

@x383494 并且由于 HLPP 强制推起点流的特性就算有负数也能过