最大权闭合子图 最大密度子图

chenzhiyv · 2025-08-26 21:49:17 · 算法·理论

marp: true color: black headingDivider: 2 math: mathjax

网络流

陈祉余

最大权闭合子图

什么是最大权闭合子图

• 给你一张图，每一个点有点权，要求选一个点就要将所有的后继全部选上，问最大权方案。

最大权闭合子图怎么做

• 可以网络流建模，我们定义和源点在一起的点为不选，和汇点在一起的点为选。每一个权值为正数的点向源点连流量为权值的边，权值为负数的点向汇点连流量为权值的绝对值的边，原图上的边连流量为inf的边，跑最小割。

• 将所有连向源点的边的流量和减去最小割，就是答案。

• 最大权闭合子图建模的核心就是将问题转化成选 A 就必须选 B 的形式。

为什么是正确的

• 可以发现，流量为inf的边一定不会被割掉，所以一旦一个前驱状态与源点在一起，它的所有后继就会跟源点在一起。

• 并且，最小割=不选的正点+选的负点的绝对值之和，正点总权值减去最小割一定最大。本质上是一种调整法

U103816 【模板】最大权闭合子图

模板，给个链接

::::info[代码]

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int M=2000+10,inf=1e17;
int h[M],ne[M<<3],to[M<<3],w[M<<3],idx=1;
int n,m;
int s,t;
void add(int u,int v,int c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void Add(int u,int v,int c)
{
    add(u,v,c);
    add(v,u,0);
}
int cur[M];
int dep[M];
bool vst[M];
bool bfs()
{
    for(int i=s;i<=t;i++)
        dep[i]=inf,vst[i]=0;
    queue<int> q;
    q.emplace(s);
    dep[s]=0;
    while(q.size())
    {
        auto u=q.front();
        q.pop();
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(dep[v]==inf&&w[i])
            {
                dep[v]=dep[u]+1;
                q.emplace(v);
            }
        }
    }
    return dep[t]!=inf;
}
int dfs(int u,int flow)
{
    if(u==t||!flow)
        return flow;
    int tmp=0;
    vst[u]=1;
    for(int &i=cur[u];i;i=ne[i])
    {
        int v=to[i];
        if(w[i]&&dep[v]==dep[u]+1&&!vst[v])
        {
            int d=dfs(v,min(flow-tmp,w[i]));
            if(d)
            {
                w[i]-=d;
                w[i^1]+=d;
                tmp+=d;
                if(tmp==flow)
                    break;
            }
        }
    }
    vst[u]=0;
    return tmp;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=t;i++)
            cur[i]=h[i];
        int d=dfs(s,inf);
        while(d)
        {
            ans+=d;
            d=dfs(s,inf);
        }
    }
    return ans;
}
signed main()
{
    cin>>n>>m;
    s=0,t=n+1;
    int ans=0;
    for(int i=1,p;i<=n;i++)
    {
        cin>>p;
        if(p>0)
        {
            ans+=p;
            Add(s,i,p);
        }
        else
            Add(i,t,-p);
    }
    for(int i=1,u,v;i<=m;i++)
    {
        cin>>u>>v;
        Add(u,v,inf);
    }
    ans-=dinic();
    cout<<ans<<endl;
    return 0;
}

::::

P4174 [NOI2006] 最大获利

问题陈述

有 n 个基站，修建代价为 p_i ，有 m 个用户，每一个用户要用基站 a_i,b_i，同时满足会有收益 c_i，问最大收益。

P4174 [NOI2006] 最大获利

解法

• 这是一个最大权闭合子图，用户要求的两个基站必须同时满足。
• 每一个用户向源点连边，流量为收益，用户向要求的两个基站连边，流量为 inf，基站向汇点连边，流量为基站代价
• 用所有用户的总收益减去最小割就是答案

::::info[代码]

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int M=55000+10,inf=1e17;
int h[M],ne[M<<3],to[M<<3],w[M<<3],idx=1;
int n,m;
int s,t;
void add(int u,int v,int c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void Add(int u,int v,int c)
{
    add(u,v,c);
    add(v,u,0);
}
int cur[M];
int dep[M];
bool vst[M];
bool bfs()
{
    for(int i=s;i<=t;i++)
        dep[i]=inf,vst[i]=0;
    queue<int> q;
    q.emplace(s);
    dep[s]=0;
    while(q.size())
    {
        auto u=q.front();
        q.pop();
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(dep[v]==inf&&w[i])
            {
                dep[v]=dep[u]+1;
                q.emplace(v);
            }
        }
    }
    return dep[t]!=inf;
}
int dfs(int u,int flow)
{
    if(u==t||!flow)
        return flow;
    int tmp=0;
    vst[u]=1;
    for(int &i=cur[u];i;i=ne[i])
    {
        int v=to[i];
        if(w[i]&&dep[v]==dep[u]+1&&!vst[v])
        {
            int d=dfs(v,min(flow-tmp,w[i]));
            if(d)
            {
                w[i]-=d;
                w[i^1]+=d;
                tmp+=d;
                if(tmp==flow)
                    break;
            }
        }
    }
    vst[u]=0;
    return tmp;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=t;i++)
            cur[i]=h[i];
        int d=dfs(s,inf);
        while(d)
        {
            ans+=d;
            d=dfs(s,inf);
        }
    }
    return ans;
}
signed main()
{
    cin>>n>>m;
    s=0,t=n+m+1;
    for(int i=1,p;i<=n;i++)
    {
        cin>>p;
        Add(i,t,p);
    }
    int ans=0;
    for(int i=1,a,b,c;i<=m;i++)
    {
        cin>>a>>b>>c;
        ans+=c;
        Add(s,i+n,c);
        Add(i+n,a,inf);
        Add(i+n,b,inf);
    }
    ans-=dinic();
    cout<<ans<<endl;
    return 0;
}

::::

P2762 太空飞行计划问题

问题陈述

P2762 太空飞行计划问题

解法

• 前面是正常的最小割问题，关键在于怎样输出方案。

• 在最后一次增广后，所有的与源点没有流量经过的点就被划分到与汇点在一起，即选上了。所以此时选上的点就是最后一次 \operatorname{bfs} 中有层数的点。

::::info[代码]

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
//#define cout io
//#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int M=1000+10,inf=1e17;
int n,m;
int h[M],to[M<<1],ne[M<<1],w[M<<1],idx=1;
int s=1,t=2;
void Add(int u,int v,int c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void add(int u,int v,int c)
{
//  cout<<u<<" "<<v<<" "<<c<<endl;
    Add(u,v,c);
    Add(v,u,0);
}
int dep[M];
int cur[M];
bool bfs()
{
    for(int i=s;i<=2+n+m;i++)
        dep[i]=inf;
    dep[s]=0;
    queue<int> q;
    q.emplace(s);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(w[i]&&dep[v]==inf)
            {
                dep[v]=dep[u]+1;
                q.emplace(v);
            }
        }
    }
    return dep[t]!=inf;
}
int dfs(int u,int flow)
{
    if(u==t||!flow)
        return flow;
    int tmp=0;
    for(int &i=cur[u];i;i=ne[i])
    {
        int v=to[i];
        if(w[i]&&dep[v]==dep[u]+1)
        {
            int d=dfs(v,min(flow-tmp,w[i]));
            if(d)
            {
                w[i]-=d;
                w[i^1]+=d;
                tmp+=d;
                if(tmp==flow)
                    break;
            }
        }
    }
    return tmp;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=2+n+m;i++)
            cur[i]=h[i];
        int d=dfs(s,inf);
        if(d)
        {
            ans+=d;
            d=dfs(s,inf);
        }
    }
    return ans;
}
signed main()
{
    cin>>m>>n;
    int ans=0;
    for(int i=1,c;i<=m;i++)
    {
        cin>>c;
        add(s,i+2,c);
        ans+=c;
        int x;
        char C;
        while(scanf("%c",&C),C==' ')
        {
            scanf("%lld",&x);
            add(i+2,2+m+x,inf);
        }
    }
    for(int i=1,c;i<=n;i++)
    {
        cin>>c;
        add(2+m+i,t,c);
    }
    ans-=dinic();
    vector<int> v1,v2;
    for(int i=2;i<=2+n+m;i++)
    {
        if(dep[i]!=inf)
        {
            if(2<i&&i<=2+m)
                v1.emplace_back(i-2);
            if(2+m+1<=i&&i<=2+m+n)
                v2.emplace_back(i-m-2);
        }
    }
    for(auto i:v1)
        cout<<i<<" ";
    cout<<endl;
    for(auto i:v2)
        cout<<i<<" ";
    cout<<endl;
    cout<<ans<<endl;
    return 0;
}

::::

P3410 拍照

问题陈述

小 B 有 N 个下属，现小 B 要带着一些下属让别人拍照。

有 M 个人，每个人都愿意付给小 B 一定钱来和 N 个下属中的一些人进行合影。如果这一些下属没带齐那么就不能拍照，小 B 也不会得到钱。

对于每个下属，如果他带了那么小 B 需要给他一些钱，保证当他拍照时配合。

CF311E biologist

解法

• 这是一个最大权闭合子图，每一个询问中的所有点必须同时选。

• 因为最大收益，所以套路的考虑总收益减去最小的不能拿到的收益，就是最小割。

• 具体的，将每一个初始性别为 0 的点连向源点，初始性别为 1 的点连向汇点，流量为改变性别的代价。

• 对于每一个询问，新建一个虚点，如果要求性别为 0，连向源点，流量为收益加上倒扣的钱，并向询问中的所有要求的点连流量为 inf 的边。

• 所有询问的总收益减去最小割就是答案

::::info[代码]

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=2e4+10,M=1e5+10,inf=1e17;
int n,m,g;
int h[N<<1],ne[M<<1],w[M<<2],to[M<<2],idx=1;
int s,t;
int a[N],v[N];
void add(int u,int v,int c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void Add(int u,int v,int c)
{
    add(u,v,c);
    add(v,u,0);
}
int cur[N<<1];
int dep[N<<1];
bool vst[N<<1];
bool bfs()
{
    for(int i=s;i<=t;i++)
        dep[i]=inf,vst[i]=0;
    queue<int> q;
    q.emplace(s);
    dep[s]=0;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(w[i]>0&&dep[v]==inf)
            {
                q.emplace(v);
                dep[v]=dep[u]+1;
            }
        }
    }
    return (dep[t]!=inf);
}
int dfs(int u,int flow)
{
    if(u==t||!flow)
        return flow;
    vst[u]=1;
    int res=0;
    for(int &i=cur[u];i;i=ne[i])
    {
        int v=to[i];
        if(w[i]&&dep[v]==dep[u]+1&&!vst[v])
        {
            int d=dfs(v,min(flow-res,w[i]));
            if(d)
            {
                w[i]-=d;
                w[i^1]+=d;
                res+=d;
                if(res==flow)
                    break;
            }
        }
    }
    vst[u]=0;
    return res;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=t;i++)
            cur[i]=h[i];
        int d=dfs(s,inf);
        while(d)
        {
            ans+=d;
            d=dfs(s,inf);
        }
    }
    return ans;
}
signed main()
{
    cin>>n>>m>>g;
    s=0,t=n+m+1;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        if(a[i])
            Add(i,t,v[i]);
        else
            Add(s,i,v[i]);
    }
    int ans=0;
//  for(int i=1,a,w,k,s;i<=m;i++)
//  {
//      cin>>a>>w>>k;
//      ans+=w;
//      for(int j=1;j<=k;j++)
//          cin>>v[j];
//      cin>>s;
//      if(a==0)
//          Add(s,i+n,w+g*s);
//      else
//          Add(i+n,t,w+g*s);
//      for(int j=1;j<=k;j++)
//      {
//          if(a==0)
//              Add(i+n,v[j],inf);
//          else
//              Add(v[j],i+n,inf);
//      }
//  }
    for(int i=1;i<=m;i++)
    {
        int opt,w,k,ss;
        cin>>opt>>w>>k;
        ans+=w;
        for(int j=1;j<=k;j++)
            cin>>v[j];
        cin>>ss;
        for(int j=1;j<=k;j++)
        {
            if(opt==0)
                Add(i+n,v[j],inf);
            else 
                Add(v[j],i+n,inf);
        }
        if(opt==0)
            Add(s,i+n,w+ss*g);
        else 
            Add(i+n,t,w+ss*g);
    }
    int num=dinic();
//  cout<<num<<endl;
    ans-=num;
    cout<<ans<<endl;
    return 0;
}

::::

P1361 小M的作物/P4313 文理分科/P1646 [国家集训队] happiness

解法

这一类题目的通法都是新建虚点来表示同时选，解法同上。

::::info[代码]

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=1000+10,M=1000*1000+100000,inf=1e17;
int n,m;
int s,t;
map<int,int> mp;
int cnt;
int id(int i)
{
    if(mp.find(i)!=mp.end())
        return mp[i];
    else
        return mp[i]=++cnt;
}
int h[M<<1],to[M<<2],ne[M<<2],w[M<<2],idx=1;
void Add(int u,int v,int c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void add(int u,int v,int c)
{
    Add(u,v,c);
    Add(v,u,0);
}
int cur[M<<1],dep[M<<1];
bool bfs()
{
    queue<int> q;
    for(int i=1;i<=cnt;i++)
        dep[i]=0;
    dep[s]=1;
    q.emplace(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(!dep[v]&&w[i])
            {
                dep[v]=dep[u]+1;
                q.emplace(v);
            }
        }
    }
    return dep[t];
}
int dfs(int u,int flow)
{
    if(u==t||!flow)
        return flow;
    int tmp=0;
    for(int &i=cur[u];i;i=ne[i])
    {
        int v=to[i];
        if(dep[v]==dep[u]+1&&w[i])
        {
            int d=dfs(v,min(w[i],flow-tmp));
            if(!d)
                dep[v]=0;
            w[i]-=d;
            w[i^1]+=d;
            tmp+=d;
            if(tmp==flow)
                break;
        }
    }
    return tmp;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=1;i<=cnt;i++)
            cur[i]=h[i];
        int d=dfs(s,inf);
        while(d)
        {
            ans+=d;
            d=dfs(s,inf);
        }
    }
    return ans;
}
signed main()
{
    s=++cnt;
    t=++cnt;
    cin>>n;
    int sum=0;
    for(int i=1,x;i<=n;i++)
    {
        cin>>x;
        add(id(i),t,x);
        sum+=x;
    }
    for(int i=1,x;i<=n;i++)
    {   
        cin>>x;
        add(s,id(i),x);
        sum+=x;
    }
    cin>>m;
    for(int i=1,k,c0,c1;i<=m;i++)
    {
        cin>>k>>c0>>c1;
        int id1=++cnt,id2=++cnt;
        for(int j=1,x;j<=k;j++)
        {
            cin>>x;
            add(id(x),id1,inf);
            add(id2,id(x),inf);
        }
        add(id1,t,c0);
        add(s,id2,c1);
        sum+=c0;
        sum+=c1;
    }
    cout<<sum-dinic()<<endl;
    return 0;
}

::::

P3749 [六省联考 2017] 寿司餐厅

问题陈述

有 n 种寿司，第 i 种寿司的类型为 a_i。

如果你吃了第 i 种到第 j 种寿司，你会得到 d_{i,j}(i \le j) 的收益。

如果你吃了 c(c>0) 个类型为 x 的寿司，你会付出 mx^2+cx 的代价 (m \in {0,1})。

最大化收益与代价的差。

P3749 [六省联考 2017] 寿司餐厅

解法

• 这道题里面限制不是很明显，先考虑观察性质。

• 发现这道题中唯一满足选了A就要选B的条件的只有同时选一个区间这一个，所以考虑每一个区间 [i,j]，[i,j] 向 [i+1,j] 和 [i,j-1] 连边，流量为 inf，再将每一个区间看作一种物品，依据权值正负向源/汇点连边。

• 现在考虑这个代价怎么表示。因为这个代价的形式非常奇特，所以考虑拆成两部分来考虑，前一部分是 x^2，后一部分是 cx。前面这一部分只要选了就必须有，所以考虑新建节点来表示，让区间 [i,i] 连向新点，流量为 inf，新点连向汇点，流量为 x^2，同时，区间 [i,i] 的收益减去 x，后就是模板。

::::info[代码]

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=100+10,M=1e5+10,inf=1e17;
int n,m;
int a[N];
int d[N][N];
int s=1,t=2;
int id[N][N],cnt=2;
int h[M],to[M<<1],ne[M<<1],w[M<<1],idx=1;
void Add(int u,int v,int c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void add(int u,int v,int c)
{
    Add(u,v,c);
    Add(v,u,0);
}
int dep[M];
int cur[M];
bool bfs()
{
    for(int i=s;i<=cnt;i++)
        dep[i]=inf;
    dep[s]=0;
    queue<int> q;
    q.emplace(s);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(w[i]&&dep[v]==inf)
            {
                dep[v]=dep[u]+1;
                q.emplace(v);
            }
        }
    }
    return dep[t]!=inf;
}
int dfs(int u,int flow)
{
    if(u==t||!flow)
        return flow;
    int tmp=0;
    for(int &i=cur[u];i;i=ne[i])
    {
        int v=to[i];
        if(w[i]&&dep[v]==dep[u]+1)
        {
            int d=dfs(v,min(flow-tmp,w[i]));
            if(d)
            {
                w[i]-=d;
                w[i^1]+=d;
                tmp+=d;
                if(tmp==flow)
                    break;
            }
        }
    }
    return tmp;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=cnt;i++)
            cur[i]=h[i];
        int d=dfs(s,inf);
        while(d)
        {
            ans+=d;
            d=dfs(s,inf);
        }
    }
    return ans;
}
signed main()
{
    cin>>n>>m;
    int maxa=0;
    for(int i=1;i<=n;i++)
        cin>>a[i],maxa=max(maxa,a[i]);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            cin>>d[i][j],id[i][j]=++cnt;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            int cost=d[i][j];
            if(i==j)
            {
                if(m)
                    add(id[i][j],cnt+a[i],inf);
                cost-=a[i];
            }
            add(id[i][j],id[i+1][j],inf);
            add(id[i][j],id[i][j-1],inf);
            if(cost>0)
                add(s,id[i][j],cost),ans+=cost;
            else
                add(id[i][j],t,-cost);
        }
    }
    if(m)
        for(int i=1;i<=maxa;i++)
            add(++cnt,t,i*i);
    ans-=dinic();
    cout<<ans<<endl;
    return 0;
}

::::

[ARC085E] MU

问题陈述

我们有 N 颗宝石，标记为 1 到 N 。

你可以执行以下任意次数(可能为零)的操作。

• 选择一个正整数 x，然后击碎所有标有 x 倍数的宝石。

然后，每打碎一个 i，如果标有 i 的宝石没有被打碎，就会得到 a_i 日元。但是， a_i 可能是负数，在这种情况下，你将被收取金钱。

通过最佳操作，您可以赚取多少日元？

[ARC085E] MU

解法

• 首先，最后最大，就要打碎的总权值最小，而网络流只能表示打碎了什么，所以要跑最小权值闭合子图。

• 考虑将所有权值取反，然后跑最大权值闭合子图，求出以后就是最小要打碎的权值的相反数。我们要求最后的最大权值，就要用总权值减去这一部分，所有加上相反数即可。

::::info[代码]

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=100+10,inf=1e17;
int n;
int s,t;
int h[N],to[N<<4],w[N<<4],ne[N<<4],idx=1;
void Add(int u,int v,int c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void add(int u,int v,int c)
{
    Add(u,v,c);
    Add(v,u,0);
}
int cur[N];
int dep[N];
bool bfs()
{
    for(int i=1;i<=t;i++)
        dep[i]=inf;
    dep[s]=0;
    queue<int> q;
    q.emplace(s);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(w[i]&&dep[v]==inf)
            {
                dep[v]=dep[u]+1;
                q.emplace(v);
            }
        }
    }
    return dep[t]!=inf;
}
int dfs(int u,int flow)
{
    if(u==t||!flow)
        return flow;
    int tmp=0;
    for(int &i=cur[u];i;i=ne[i])
    {
        int v=to[i];
        if(w[i]&&dep[v]==dep[u]+1)
        {
            int d=dfs(v,min(w[i],flow-tmp));
            if(d)
            {
                w[i]-=d;
                w[i^1]+=d;
                tmp+=d;
                if(tmp==flow)
                    break;
            }
        }
    }
    return tmp;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=1;i<=t;i++)
            cur[i]=h[i];
        int d=dfs(s,inf);
        while(d)
        {
            ans+=d;
            d=dfs(s,inf);
        }
    }
    return ans;
}
signed main()
{
    cin>>n;
    s=n+1,t=s+1;
    int ans=0,sum=0;
    for(int i=1,a;i<=n;i++)
    {
        cin>>a;
        sum+=a;
        a=-a;
        if(a>0)
            add(s,i,a),ans+=a;
        else
            add(i,t,-a);
    }
    for(int i=1;i<=n;i++)
        for(int j=i<<1;j<=n;j+=i)
            add(i,j,inf);
    ans-=dinic();
    sum+=ans;
    cout<<sum<<endl;
    return 0;
}

::::

P2805 [NOI2009] 植物大战僵尸

问题陈述

一个 n \times m 的矩阵，每一个位置上有植物，你操控僵尸进攻。消灭一个植物的方式是走到那个植物的位置上。消灭植物会获得一个能量值，能量值有正有负。植物可以攻击一些位置，植物的攻击力是无限大，走上去，来不及攻击就会被消灭。僵尸只能从一行的最右边走到最左边。问最大能量收入。

P2805 [NOI2009] 植物大战僵尸

解法

• 一样考虑限制，容易得到要消灭这个位置的植物，一定要先消灭保护着这个位置的植物，所以被保护的植物向保护它的植物连边，流量为 inf。 走到左边就必须经过右边，所以每一行，向自己右边的那一个格子连流量为 inf 的边。其余按照正常点权连边即可。

• 但这样过不了样例。发现在这种情况时，会发生错误： 本来 A,B 都不能被攻击到，但是当有点连向 A 时，可能不经过整个环就流走了，所以在建边之前用拓扑排序去掉所有环，再建图。

::::info[代码]

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=(20*30)+10,M=5e6+10,inf=1e17;
int h[N],to[M],ne[M],w[M],idx=1;
int in[N];
int sc[N];
vector<int> at[N];
int n,m;
int s=1,t=2;
int cnt=2;
map<pair<int,int>,int> mp;
int id(int x,int y)
{
    if(mp.find(make_pair(x,y))!=mp.end())
        return mp[make_pair(x,y)];
    else
        return mp[make_pair(x,y)]=++cnt;
}
void Add(int u,int v,int c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void add(int u,int v,int c)
{
//  cout<<u<<" "<<v<<" "<<c<<endl;
    Add(u,v,c);
    Add(v,u,0);
}
bool vst[N];
void topsort()
{
    queue<int> q;
    for(int i=3;i<=cnt;i++)
    {
        if(!in[i])
        {
            q.emplace(i);
            vst[i]=1;
        }
    }
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(auto i:at[u])
        {
            in[i]--;
            if(in[i]==0&&!vst[i])
                q.emplace(i),vst[i]=1;
        }
    }
}
int dep[N];
int cur[N];
bool bfs()
{
    for(int i=s;i<=cnt;i++)
        dep[i]=inf;
    dep[s]=0;
    queue<int> q;
    q.emplace(s);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(dep[v]==inf&&w[i])
            {
                dep[v]=dep[u]+1;
                q.emplace(v);
            }
        }
    }
    return dep[t]!=inf;
}
int dfs(int u,int flow)
{
    if(u==t||!flow)
        return flow;
    int tmp=0;
    for(int &i=cur[u];i;i=ne[i])
    {
        int v=to[i];
        if(dep[v]==dep[u]+1&&w[i])
        {
            int d=dfs(v,min(flow-tmp,w[i]));
            if(d)
            {
                w[i]-=d;
                w[i^1]+=d;
                tmp+=d;
                if(tmp==flow)
                    break;
            }
        }
    }
    return tmp;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=cnt;i++)
            cur[i]=h[i];
        int d=dfs(s,inf);
        while(d)
        {
            ans+=d;
            d=dfs(s,inf);
        }
    }
    return ans;
}
signed main()
{
    cin>>n>>m;
    for(int i=1,w,r,c;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>sc[id(i,j)];
            cin>>w;
            for(int k=1;k<=w;k++)
            {
                cin>>r>>c;
                r++;c++;
                at[id(i,j)].emplace_back(id(r,c));
                in[id(r,c)]++;
            }
            if(j<m)
            {
                at[id(i,j+1)].emplace_back(id(i,j));
                in[id(i,j)]++;
            }
        }
    }
    topsort();
    int ans=0;
    for(int i=3;i<=cnt;i++)
    {
        if(!vst[i])
            continue;
        if(sc[i]<0)
            add(i,t,-sc[i]);
        else
            add(s,i,sc[i]),ans+=sc[i];
        for(auto j:at[i])
            if(vst[j])
                add(j,i,inf);
    }
//  for(auto i:at[6])
//      cout<<i<<endl;
//  cout<<vst[5]<<" "<<vst[6]<<endl;
    ans-=dinic();
    cout<<ans<<endl;
    return 0;
}

::::

最大密度子图

什么是最大密度子图

• 定义一个图的密度为边数除以点数，现在给你一张图，求一个密度最大的子图。

最大密度子图怎么做

• 首先，这是一个 0/1 分数规划问题，可以二分解决。

• 我们设 |E| 为边数，|V| 为点数， g 为比值的最大值，有 \frac {|E|}{|V|} < g，所以 |E| < |V| \times g，|E|-|V| \times g < 0，所以只用找出 |E|-|V| \times g 的最大值即可。

• 这个式子可以直接转化为最大权闭合子图的问题，当选了一条边时，这一条边的两的端点也会被选上。所以将原图的每一个点赋点权 -g，原图的边建立一个新点，权值为 1，并向两个端点连边，最大权闭合子图就是最大值。

UVA1389 Hard Life

问题陈述

John 是某公司的 CEO。公司内部共 n 个员工，员工之间可能曾经因为小事有了过节，总是闹矛盾。

若员工 u 和员工 v 有矛盾，用边 (u,v) 表示，共 m 个矛盾。

最近，该公司内部越来越不团结，John 决定裁员。他想得到一个被裁人员的清单，使得被裁人员间的不团结率最高。

不团结率定义为被裁人员间的矛盾总数与被裁人员数的比值（不团结率 = 被裁人员之间的矛盾总数 / 被裁人员数）。

输出方案。

UVA1389 Hard Life

解法

• 最大密度子图模板。输出方案就像之前最大全闭合子图一样输出即可。

::::info[代码]

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
//#define cout io
//#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=100+10,M=1e5+10,inf=1e17;
const double eps=1e-6;
int n,m;
pair<int,int> edge[M];
int s=1,t=2;
int h[M],to[M<<4],ne[M<<4],idx=1;
double w[M<<4];
void Add(int u,int v,double c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void add(int u,int v,double c)
{
//  cout<<u<<" "<<v<<" "<<c<<endl;
    Add(u,v,c);
    Add(v,u,0);
}
void init()
{
    for(int i=0;i<=idx;i++)
        to[i]=ne[i]=w[i]=0;
    for(int i=s;i<=2+n+m;i++)
        h[i]=0;
    idx=1;
}
int build(double g)
{
    int ans=0;
    init();
    for(int i=1;i<=n;i++)
        add(i+2,t,g);
    for(int i=1;i<=m;i++)
    {
        add(s,2+n+i,1);
        ans++;
        add(2+n+i,2+edge[i].first,inf);
        add(2+n+i,2+edge[i].second,inf);
    }
    return ans;
}
int dep[M];
int cur[M];
bool bfs()
{
    for(int i=s;i<=2+n+m;i++)
        dep[i]=inf;
    dep[s]=0;
    queue<int> q;
    q.emplace(s);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(dep[v]==inf&&w[i])
            {
                dep[v]=dep[u]+1;
                q.emplace(v);
            }
        }
    }
    return dep[t]!=inf;
}
double dfs(int u,double flow)
{
    if(u==t||!flow)
        return flow;
    double tmp=0;
    for(int &i=cur[u];i;i=ne[i])
    {
        int v=to[i];
        if(w[i]&&dep[v]==dep[u]+1)
        {
            double d=dfs(v,min(w[i],flow-tmp));
            if(d)
            {
                w[i]-=d;
                w[i^1]+=d;
                tmp+=d;
                if(tmp==flow)
                    break;
            }
        }
    }
    return tmp;
}
double dinic()
{
    double ans=0;
    while(bfs())
    {
        for(int i=s;i<=2+n+m;i++)
            cur[i]=h[i];
//      cout<<endl;
        double d=dfs(s,inf);
        while(d)
        {
//          cout<<d<<endl;
            ans+=d;
            d=dfs(s,inf);
        }
    }
    return ans;
}
double check(double g)
{
    double ans=build(g);
    ans-=dinic();
    return ans;
}
signed main()
{
    while(cin>>n>>m)
    {
        for(int i=1;i<=m;i++)
            cin>>edge[i].first>>edge[i].second;
        double l=0,r=m;
        while(r-l>eps)
        {
            double mid=(l+r)/2.0;
            if(check(mid)>0)
                l=mid;
            else
                r=mid;
        }
        check(l);
        vector<int> ans;
        for(int i=3;i<=2+n+m;i++)
            if(dep[i]!=inf&&i<=2+n)
                    ans.emplace_back(i-2);
        if(ans.size()==0)
        {
            cout<<1<<endl<<1<<endl;
            continue;
        }
        cout<<ans.size()<<endl;
        for(int i:ans)
            cout<<i<<endl;
        cout<<endl;
    }
    return 0;
}

::::

[Gym-100548C] The Problem Needs 3D Arrays

问题陈述

一个排列是由 n 个不同的正整数组成的序列 p_1, p_2, . . . , p_n，且每个整数都不超过 n。假设序列 S 的 r(S) 表示序列 S 中的逆序对数量（如果 i < j 且 S_i > S_j，则称 (i， j) 为 S 的一个逆序对），l(S) 表示序列 S 的长度。给定长度为 n 的排列 P，你的任务是找到 P 的一个子序列 S，使得 \frac{r(S)}{l(S)} 的值最大。P 的子序列是满足 0 < i_1 < i_2 < . . . < i_t ≤ n 的序列 (p_{i1}， p_{i2}， . . . ， p_{it})。

[Gym-100548C] The Problem Needs 3D Arrays

解法

这也是比较板的一道题，将原序列的逆序对提出来，建成边，直接跑最大密度子图。

::::info[代码]

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
//#define cout io
//#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=100+10,M=1e5+10,inf=1e17;
const double eps=1e-8;
int n,m;
pair<int,int> edge[M];
int s=1,t=2;
int h[M],to[M<<4],ne[M<<4],idx=1;
int p[N];
double w[M<<4];
void Add(int u,int v,double c)
{
    to[++idx]=v;
    w[idx]=c;
    ne[idx]=h[u];
    h[u]=idx;
}
void add(int u,int v,double c)
{
    Add(u,v,c);
    Add(v,u,0);
}
void init()
{
    for(int i=0;i<=idx;i++)
        to[i]=ne[i]=w[i]=0;
    for(int i=s;i<=2+n+m;i++)
        h[i]=0;
    idx=1;
}
int build(double g)
{
    int ans=0;
    init();
    for(int i=1;i<=n;i++)
        add(i+2,t,g);
    for(int i=1;i<=m;i++)
    {
        add(s,2+n+i,1);
        ans++;
        add(2+n+i,2+edge[i].first,inf);
        add(2+n+i,2+edge[i].second,inf);
    }
    return ans;
}
int dep[M];
int cur[M];
bool bfs()
{
    for(int i=s;i<=2+n+m;i++)
        dep[i]=inf;
    dep[s]=0;
    queue<int> q;
    q.emplace(s);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=ne[i])
        {
            int v=to[i];
            if(dep[v]==inf&&w[i])
            {
                dep[v]=dep[u]+1;
                q.emplace(v);
            }
        }
    }
    return dep[t]!=inf;
}
double dfs(int u,double flow)
{
    if(u==t||!flow)
        return flow;
    double tmp=0;
    for(int &i=cur[u];i;i=ne[i])
    {
        int v=to[i];
        if(w[i]&&dep[v]==dep[u]+1)
        {
            double d=dfs(v,min(w[i],flow-tmp));
            if(d)
            {
                w[i]-=d;
                w[i^1]+=d;
                tmp+=d;
                if(tmp==flow)
                    break;
            }
        }
    }
    return tmp;
}
double dinic()
{
    double ans=0;
    while(bfs())
    {
        for(int i=s;i<=2+n+m;i++)
            cur[i]=h[i];
        double d=dfs(s,inf);
        while(d)
        {
            ans+=d;
            d=dfs(s,inf);
        }
    }
    return ans;
}
double check(double g)
{
    double ans=build(g);
    ans-=dinic();
    return ans;
}
signed main()
{
    int T;
    cin>>T;
    for(int kk=1;kk<=T;kk++)
    {
        cin>>n;
        m=0;
        for(int i=1;i<=n;i++)
            cin>>p[i];
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                if(p[i]>p[j])
                    edge[++m]=make_pair(i,j);
        double l=0,r=m;
        while(r-l>eps)
        {
            double mid=(l+r)/2.0;
            if(check(mid)>0)
                l=mid;
            else
                r=mid;
        }
        cout<<fixed<<setprecision(10)<<"Case #"<<kk<<": "<<l<<endl;
    }
    return 0;
}

::::

Maximum average Sequence

‌题目描述‌

众所周知，华中科技大学校园内有无数树木。 给定一个数字序列 a_1, a_2, ..., a_n，请找出这些数字的一个子序列，使其平均序列值最大。平均序列的定义是：满足 u 能整除 v 或 v 能整除 u 的数对数量，除以该子序列的长度。 例如，在序列 {1,2,3,4} 中，最大平均序列是 {1,2,4}。共有三对数(<1,2>,<1,4>,<2,4>)满足 u 能整除 v 或 v 能整除 u，且子序列长度为 3，因此答案为 3 \div 3=1。