bzoj3550

费用流+线性规划

搞了很长时间。。。

我们可以设立式子，a[1]+a[2]+a[3]+...+a[n]<=k , ... , a[2 * n + 1]+ ... +a[3*n]<=k

a是指该位有没有选

那么我们添加一个辅助变量f

a[1]+a[2]+a[3]+...+a[n]+f[1]=k,

...

a[2*n+1]+...+a[3*n]+f[2*n+1]=k

我们就得到了2n+1个式子

然后我们添加两个式子a(0):0=0 a(2*n+2):0=0

然后差分得到2n+2个式子,后一个式子减前一个式子

0:a[1]+a[2]+...+a[n]+f[1]=k

1:a[2]+...+a[n+1]+f[2]-a[1]-...-a[n]-f[1]=0->a[n+1]+f[2]-a[1]-f[1]=0

2:a[n+2]+f[3]-a[2]-f[2]=0

...

2n+1:a[3*n]+f[2*n+1]-a[2*n]-f[2*n]

2n+2:a[2n+1]+...+a[3*n]+f[2*n+1]=k

然后这个式子很像网络流的流量平衡，于是这样建图，正对负，负对正，因为第0项是a[1]+...+a[n],所以0->[1,n],因为都是这样形式的a[n+1]+f[2]-a[1]-f[1],-a[1]和+a[1]对应，因为a∈[0,1],所以流量为1，a[i]=1是指选了a[i],所以费用为a[i]

i-1->i,因为相邻两项-f[i],+f[i],f[i]∈[0,k],因为是辅助变量，所以什么都没有对应，流量为k,费用为0

后面类似然后就建好图了设立源汇和1n相连，流量为k 感觉理解不够深刻碰见这种序列+限制的题可以用费用流做，先把限制代数化，然后-+连边，一般还会相邻的点之间连边，这样可以解决一些序列的问题，以后碰见再做

#include<bits/stdc++.h>

using namespace std;

const int N = , inf = 0x3f3f3f3f;

struct edge {

    int nxt, to, f, c;

} e[N * ];

int n, m, k, source, sink, tot, cnt = , sum;

int a[N], head[N], d[N], pree[N], prev[N], vis[N], live[N], dead[N], day[N], c[N], l[N], p[N];

inline void link(int u, int v, int f, int c)

{

    e[++cnt].nxt = head[u];

    head[u] = cnt;

    e[cnt].f = f;

    e[cnt].to = v;

    e[cnt].c = c;

}

inline void insert(int u, int v, int f, int c)

{

    link(u, v, f, c);

    link(v, u, , -c);

}

bool spfa()

{

    memset(d, -, sizeof(d));

    d[source] = ;

    queue<int> q;

    q.push(source);

    while(!q.empty())

    {

        int u = q.front();

        q.pop();

        vis[u] = ;

        for(int i = head[u]; i; i = e[i].nxt) if(e[i].f && (d[e[i].to] < d[u] + e[i].c || d[e[i].to] == -))

        {

            pree[e[i].to] = i;

            prev[e[i].to] = u;

            d[e[i].to] = d[u] + e[i].c;

            if(vis[e[i].to] == )

            {

                q.push(e[i].to);

                vis[e[i].to] = ;

            }

        }

    }

    return d[sink] != -;

}

inline int Edmonds_Karp()

{

    int ans = ;

    while(spfa())

    {

        int now = sink, delta = inf;

        while(now != source)

        {

            delta = min(delta, e[pree[now]].f);

            now = prev[now];

        }

        now = sink;

        while(now != source)

        {

            e[pree[now]].f -= delta;

            e[pree[now] ^ ].f += delta;

            now = prev[now];

        }

        ans += delta * d[sink];

    }

    return ans;

}

int main()

{

    scanf("%d%d", &n, &k);

    for(int i = ; i <=  * n; ++i) scanf("%d", &a[i]);

    source =  * n + ;

    sink =  * n + ;

    int s = , t =  * n + ;

    insert(source, s, k, );

    insert(t, sink, k, );

    sink =  * n + ;

    for(int i = ; i <= n; ++i) insert(s, i, , a[i]);

    for(int i = ; i <=  * n + ; ++i) insert(i - , i, k, );

    for(int i = n + ; i <=  * n; ++i) insert(i, t, , a[i + n]);

    for(int i = n + ; i <=  * n; ++i) insert(i - n, i, , a[i]);    

/*    for(int i = 1; i <= 2 * n + 1; ++i) insert(i - 1, i, k, 0);

    for(int i = 1; i <= n; ++i)

    {

        insert(s, i, 1, a[i]);

        insert(i, i + n, 1, a[i + n]);

        insert(i + n, t, 1, a[i + 2 * n]);

    } */

    printf("%d\n", Edmonds_Karp());

    return ;

}

巴特西

bzoj3550

最新文章

热门文章