头像

艾特玖




离线:16小时前


最近来访(168)
用户头像
秦末
用户头像
涸塘旷野
用户头像
Galen_FuckPPT
用户头像
Nan97
用户头像
景云
用户头像
RyanMoriarty
用户头像
yxc
用户头像
三四
用户头像
YikN
用户头像
bruhify
用户头像
caidd
用户头像
慢冷.
用户头像
众生皆苦
用户头像
Nanfeng1997.
用户头像
逍遥er
用户头像
1746705086
用户头像
心向远方
用户头像
sakuragod
用户头像
彩色铅笔
用户头像
陈平安

活动打卡代码 AcWing 2324. 生活的艰辛

艾特玖
16小时前

最大密度子图

具体实现建图,看代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110,M = (1000+N*2)*2,INF = 1e8;
int h[N],e[M],ne[M],idx;
double f[M];
int d[N],cur[N],dag[N],q[N];
PII edges[M];
int ans;
bool st[N];
int n,m,S,T;

void add(int a,int b,double c1,double c2)
{
    e[idx]=b,ne[idx]=h[a],f[idx] = c1,h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],f[idx] = c2,h[b]=idx++;
}

void build(double g)
{
    memset(h, -1, sizeof h);
    idx = 0;
    for(int i=0;i<m;i++) add(edges[i].first,edges[i].second,1,1);//没有边权,则边与边之间加边,边权为1,若有边权,则增加对应边权
    for(int i=1;i<=n;i++)
    {
        add(S,i,m,0);//从S向每个点,连接边权为U的偏移量,U大于2*g-dv最大值
        add(i,T,m+2*g-dag[i],0);//从每个点向T连接边权为U+2*g-dv的边,此时是没有点权的情况,若有点权,则增加U+2*g-dv-2*pv,pv为对应点权
    }
}

bool bfs()
{
    int hh = 0,tt = -1;
    memset(d,-1,sizeof d);
    d[S] = 0,cur[S] = h[S],q[++tt] = S;
    while(hh<=tt)
    {
        auto t = q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&f[i]>0)
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j==T) return 1;
                q[++tt]=j;
            }
        }
    }
    return 0;
}

double find(int u,double limit)
{
    if(u==T) return limit;
    double flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if(d[j]==d[u]+1&&f[i]>0)
        {
            double t = find(j,min(f[i],limit - flow));
            if(t<=0) d[j] = -1;
            f[i] -= t,f[i^1] += t,flow += t;
        }
    }
    return flow;
}

double dinic(double mid)
{
    build(mid);
    double r = 0,flow;
    while(bfs()) while(flow=find(S,INF)) r+=flow;
    return r;
}

void dfs(int u)
{
    st[u] = 1;
    if(u!=S) ans++;
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(!st[j]&&f[i]>0) dfs(j);//从源点沿着正向边,能走到的所有点都是合法解中的点
    }
}

int main()
{
    cin>>n>>m;
    S = 0,T = n + 1;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        edges[i] = {a,b};
        dag[a]++,dag[b]++;
    }
    double l = 0,r = m;
    while(r-l>1e-8)
    {
        double mid = (r+l)/2;
        double t = dinic(mid);
        if(m*n-t>0) l = mid;
        else r = mid;
    }
    dinic(l);
    dfs(S);

    if(!ans) cout<<"1\n1";
    else 
    {
        cout<<ans<<endl;
        for(int i=1;i<=n;i++)
            if(st[i])
                cout<<i<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 961. 最大获利

模型:
最大权闭合子图

结论:
$c(S,T)(最小割)+w(最大权闭合子图)=w_{v^+}(图中所有正权节点权值和)$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 55010,M = (N+1000000)*2,INF = 1e8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
int n,m,S,T;

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
    e[idx] = a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}

bool bfs()
{
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S] = 0,cur[S] = h[S],q.push(S);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j==T) return 1;
                q.push(j);
            }
        }
    }
    return 0;
}

int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if(d[j]==d[u]+1&&w[i])
        {
            int t = find(j,min(w[i],limit-flow));
            if(!t) d[j] = -1;
            w[i] -= t,w[i^1] += t,flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0,flow;
    while(bfs()) while(flow=find(S,INF)) r+=flow;
    return r;
}

int main()
{
    cin>>n>>m;
    memset(h, -1, sizeof h);
    S = 0,T = n + m + 1;
    LL res = 0;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        add(i,T,x);
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(i+n,a,INF),add(i+n,b,INF),add(S,i+n,c);
        res+=c;
    }
    cout<<res - dinic()<<endl;
    return 0;
}


活动打卡代码 AcWing 2280. 最优标号

建图:
依据位运算的特点,每一位的运算都是独立的。
枚举每一位:
对每一个点,根据在点在该位上的值,分别分在0,1两个割集中。
根据异或运算的特点,在同一个集合中的边,异或后为0,而位于不同集合的两个点,异或后值为1.
则想要让总花费最少,则对应的最小割最小,即代表这一位的花费最小

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 510,M = (3000+N*2)*2,INF = 1e8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
LL p[N];
PII edges[M];
int n,m,k,S,T;

void add(int a,int b,int c1,int c2)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c1,h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],w[idx]=c2,h[b]=idx++;
}

void build(int k)
{
    memset(h,-1,sizeof h);
    idx = 0;
    for(int i=0;i<m;i++)
        add(edges[i].first,edges[i].second,1,1);
    for(int i=1;i<=n;i++)
        if(p[i])
        {
            if(p[i]>>k&1) add(i,T,INF,0);
            else add(S,i,INF,0);
        }
}

bool bfs()
{
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S] = 0,cur[S] = h[S],q.push(S);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j==T) return 1;
                q.push(j);
            }
        }
    }
    return 0;
}

int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if(d[j]==d[u]+1&&w[i])
        {
            int t = find(j,min(w[i],limit-flow));
            if(!t) d[j] = -1;
            w[i] -= t,w[i^1] += t,flow += t;
        }
    }
    return flow;
}

LL dinic(int k)
{
    build(k);
    int r =0,flow;
    while(bfs()) while(flow=find(S,INF)) r+=flow;
    return r;
}

int main()
{
    cin>>n>>m;
    S = 0,T = n + 1;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        edges[i]={a,b};
    }
    cin>>k;
    while(k--)
    {
        int a,b;cin>>a>>b;
        p[a]=b;
    }
    LL res = 0;
    for(int i=0;i<=30;i++) res+=dinic(i)<<i;
    cout<<res<<endl;
    return 0;
}




活动打卡代码 AcWing 2279. 网络战争

题解推荐看 whsstory 大佬的

#include<bits/stdc++.h>
using namespace std;
const int N = 110,M = 810,INF = 1e8;
const double eps = 1e-8;
int h[N],e[M],ne[M],w[M],idx;
double f[M];
int d[N],cur[N];
int n,m,S,T;

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a]=idx++;
    e[idx] = a,ne[idx] = h[b],w[idx] = c,h[b]=idx++;
}

double find(int u,double limit)
{
    if(u==T) return limit;
    double flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if(d[j]==d[u]+1&&f[i]>0)
        {
            double t = find(j,min(f[i],limit-flow));
            if(t<eps) d[j] = -1;
            f[i] -= t,f[i^1] += t,flow += t;
        }
    }
    return flow;
}

bool bfs()
{
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S] = 0,cur[S] = h[S],q.push(S);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&f[i]>0)
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j==T) return 1;
                q.push(j);
            }
        }
    }
    return 0;
}

double dinic(double mid)
{
    double res = 0;
    for(int i=0;i<idx;i+=2)
        if(w[i]<=mid) 
        {
            res+=w[i]-mid;
            f[i] = f[i^1] = 0;
        }
        else f[i] = f[i^1] = w[i] - mid;
    double r = 0,flow;
    while(bfs()) while(flow=find(S,INF)) r+=flow;
    return r + res;
}

int main()
{
    cin>>n>>m>>S>>T;
    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    double l = 0,r = 1e7;
    while(r-l>eps)
    {
        double mid = (l+r)/2;
        if(dinic(mid)<0) r = mid;
        else l = mid;
    }
    printf("%.2lf\n",r);
    return 0;
}



依据最大流最小割定理
最大流=最小割

#include<bits/stdc++.h>
using namespace std;
const int N = 10010,M = 200010,INF = 1e8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
int n,m,S,T;

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a]=idx++;
    e[idx] = a,ne[idx] = h[b],w[idx] = 0,h[b]=idx++;
}

bool bfs()
{
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S] = 0,cur[S] = h[S],q.push(S);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&w[i]) 
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j==T) return 1;
                q.push(j);
            }
        }
    }
    return 0;
}

int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if(d[j]==d[u]+1&&w[i])
        {
            int t = find(j,min(w[i],limit-flow));
            if(!t) d[j]=-1;
            w[i] -= t,w[i^1] += t,flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0,flow;
    while(bfs()) while(flow = find(S,INF)) r+=flow;
    return r;
}

int main()
{
    cin>>n>>m>>S>>T;
    memset(h, -1, sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dinic()<<endl;
    return 0;
}


活动打卡代码 AcWing 1945. 奶牛棒球

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int d[N];

int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++) cin>>d[i];
    sort(d,d+n);
    int ans = 0;
    for(int i=0;i<n-2;i++){
        for(int j=i+1;j<n-1;j++)
        {
            int dist = d[j] - d[i];
            int x1 = d[j] + dist,x2 = d[j] + dist*2;
            int d1 = lower_bound(d,d+n,x1) - d,d2 = upper_bound(d,d+n,x2) - d;
            ans+=d2-d1;
        }
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 2237. 猪

分析:
巧妙的建图。先分析题目,我们需要求按照顾客来的顺序,能够卖出去的最多的猪的数量。
我们有几个问题需要解决:
1.每次顾客来了之后,如何实现,猪舍之间猪的调整。
2.如何实现顾客的次序关系
将两个问题混合在一起考虑,我们构造了如下的图。
按按次序,对一个顾客,看他手中有的钥匙对应的猪舍,分为两种情况
1.若从未被光顾,则直接从源点连接一条边到该顾客,容量为对应猪舍的猪的数量。
2.若已经被光顾过,则从上一个光顾的客人连一条边,容量为INF。
(可以理解为需要从一个顾客操作完之后的结果来选择)
这样就完成了时序的建立。
这可以给出一个启示,若是有先后顺序的点,则可以通过建边来完成时序的建立

#include<bits/stdc++.h>
using namespace std;
const int N = 110,M = 20200,INF = 1e8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
int g[1010],last[1010];
int m,n,S,T;

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}

bool bfs()
{
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S] = 0,cur[S] = h[S],q.push(S);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j==T) return 1;
                q.push(j);
            }
        }
    }
    return 0;
}

int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if(d[j]==d[u]+1&&w[i])
        {
            int t = find(j,min(w[i],limit-flow));
            if(!t) d[j] = -1;
            w[i] -= t,w[i^1] += t,flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0,flow;
    while(bfs()) while(flow=find(S,INF)) r+=flow;
    return r;
}

int main()
{
    cin>>m>>n;
    memset(h, -1, sizeof h);
    S = 0,T = n + 1;
    for(int i=1;i<=m;i++) cin>>g[i];
    for(int i=1;i<=n;i++)
    {
        int a;cin>>a;
        while(a--)
        {
            int id;cin>>id;
            if(!last[id]) add(S,i,g[id]);
            else add(last[id],i,INF);
            last[id] = i;
        }
        int b;cin>>b;
        add(i,T,b);
    }

    cout<<dinic()<<endl;
    return 0;
}


活动打卡代码 AcWing 2278. 企鹅游行

知识点
拆点,最大流

分析:
通过从源点连边限制初始每块冰上的企鹅数量,同时通过拆点来限制每个点被用的次数。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define fi first
#define se second
const int N = 210,M = 21000,INF = 1e8;
const double eps = 1e-8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
PII p[N];
int n,S,T;
double D;

bool check(PII a,PII b)
{
    double dx = a.fi - b.fi,dy = a.se - b.se;
    return dx*dx + dy*dy <= D*D + eps;
}

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}

bool bfs()
{
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S] = 0,cur[S] = h[S],q.push(S);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j==T) return 1;
                q.push(j);
            }
        }
    }
    return 0;
}

int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]  = i;
        int j = e[i];
        if(d[j]==d[u]+1&&w[i])
        {
            int t = find(j,min(w[i],limit-flow));
            if(!t) d[j] = -1;
            w[i] -= t,w[i^1] += t,flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0,flow;
    while(bfs()) while(flow = find(S,INF)) r+=flow;
    return r;
}

int main()
{
    int Case;
    scanf("%d",&Case);
    while(Case--)
    {
        scanf("%d%lf",&n,&D);
        memset(h, -1, sizeof h);
        idx=0,S=0;
        int tot = 0;
        for(int i=1;i<=n;i++)
        {
            int x,y,a,b;
            scanf("%d%d%d%d",&x,&y,&a,&b);
            tot+=a;
            p[i] = {x,y};
            add(S,i,a);
            add(i,i+n,b);
        }
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                if(check(p[i],p[j]))
                {
                    add(i+n,j,INF);
                    add(j+n,i,INF);
                }
        int cnt = 0;
        for(int i=1;i<=n;i++)
        {
            T = i;
            for(int i=0;i<idx;i+=2)
            {
                w[i] += w[i^1];
                w[i^1] = 0;
            }
            if(dinic()==tot)
            {
                printf("%d ",i-1);
                cnt++;
            }
        }
        if(cnt) puts("");
        else puts("-1");
    }
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
const int N = 1010,M = 251010,INF = 1e8;
int h[N],e[M],ne[M],w[M],idx;
int d[N],cur[N];
int f[N],g[N];
int n,s,S,T;

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],w[idx]=0,h[b]=idx++;
}

bool bfs()
{
    queue<int> q;
    memset(d,-1,sizeof d);
    d[S] = 0,cur[S] = h[S],q.push(S);
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if(d[j]==-1&&w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if(j==T) return 1;
                q.push(j);
            }
        }
    }
    return 0;
}

int find(int u,int limit)
{
    if(u==T) return limit;
    int flow = 0;
    for(int i=cur[u];~i;i=ne[i])
    {
        int j = e[i];
        if(d[j]==d[u]+1&&w[i])
        {
            int t = find(j,min(w[i],limit-flow));
            if(!t) d[j] = -1;
            w[i] -= t,w[i^1] +=t,flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0,flow;
    while(bfs()) while(flow=find(S,INF)) r+=flow;
    return r;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>g[i];
    memset(h, -1, sizeof h);
    S = 0,T = n*2 + 1;
    int s = 0;
    for(int i=1;i<=n;i++)
    {
        add(i,i+n,1);
        f[i]=1;
        for(int j=1;j<i;j++)
            if(g[i]>=g[j])
                f[i]=max(f[i],f[j]+1);
        for(int j=1;j<i;j++)
            if(g[i]>=g[j]&&f[i]==f[j]+1)
                add(j+n,i,1);
        s=max(s,f[i]);
        if(f[i]==1) add(S,i,1);
    }

    for(int i=1;i<=n;i++)
        if(f[i]==s)
            add(i+n,T,1);

    cout<<s<<endl;
    if(s==1) cout<<n<<endl<<n<<endl;
    else 
    {
        int res = dinic();
        cout<<res<<endl;
        for (int i = 0; i < idx; i += 2)
        {
            int a = e[i ^ 1], b = e[i];
            if (a == S && b == 1) w[i] = INF;//从源点向第一个点连的边
            else if (a == 1 && b == n + 1) w[i] = INF;//从第一个点的入点向出点连的边
            else if (a == n && b == n + n) w[i] = INF;//从最后一个点的入点像出点连的边
            else if (a == n + n && b == T) w[i] = INF;//从最后一个点向汇点连的边
        }
        cout<<res+dinic()<<endl;
    }
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,y,z;
    cin>>n>>x>>y>>z;
    map<int,int> mp,mp1,mp2;
    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        mp[a]++,mp[b]++;
        mp1[a]++,mp2[b]++;
    }
    int res = 0,sum = 0,ans = 0;
    //res温度低的数量,sum适宜的数量,n-sum-res高温的数量
    for(auto it:mp)
    {
        sum+=mp1[it.first];
        ans=max(ans,res*z+sum*y+(n-res-sum)*x);
        res+=mp2[it.first];
        sum-=mp2[it.first];
    }
    cout<<ans<<endl;
    return 0;
}