头像

小树苗

xcgz




离线:1天前


最近来访(23)
用户头像
AcWing2AK
用户头像
我怀念的
用户头像
rd0
用户头像
天才小笼包
用户头像
不拿NOI金牌不改名
用户头像
山猫Plus
用户头像
zfs
用户头像
uhgariej
用户头像
焱鶘
用户头像
MIKASA
用户头像
luxcgo
用户头像
zhangjh024
用户头像
aiyaya
用户头像
cdm
用户头像
xiao天
用户头像
fuchen112
用户头像
福宝j
用户头像
aaaaaaaaa_3
用户头像
天南星魔芋


小树苗
2021-07-09 15:44

集合S中的数出现奇数次的数有k个的方案数怎么用生成函数求




小树苗
2021-06-19 08:03

dinic等算法可以跑流量为负的图吗




小树苗
2021-05-31 10:21

一样的值,一样的double,一样的printf(“%.2lf”)
为什么一个是.82,一个是.83啊,cout输出出来一样.825,这怎么改,我崩溃了!!!!
输出的时候-0.001,-0.005,-0.004都不行,啊啊啊!!!!!




小树苗
2021-04-19 13:24

同样的代码,第一回tle,第二回wa,第一回过了18个点,第二回就15个点了???
数据还会变的吗???



新鲜事 原文

小树苗
2021-04-02 14:20
今天才知道,求全排列,用dfs,不要next_permutation,next_permutation时间复杂度O(n),会t飞的



小树苗
2021-03-23 14:42

按照公式分k&1,s(k/2)+a^(k/2)s(k/2+1)求,tle,但是转化成a+as(k-1) 就跑得飞快???



分享 图论神器

小树苗
2021-03-20 14:52



小树苗
2021-03-17 09:19

缺少一组从重心伸出来的链。
4 3
0 1 1
1 2 3
1 3 4
用之前能A的代码跑出来-1
但实际上是1



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

小树苗
2020-09-26 15:27
#include<bits/stdc++.h>
using namespace std;
const int N=100+5;
const int M=400+5;
const double eps=1e-8;
int tot=1;
int head[N],to[M*2],next1[M*2];
double val[M*2];
double w[M*2];
void lian(int x,int y,double v)
{
    to[++tot]=y;
    next1[tot]=head[x];
    head[x]=tot;
    val[tot]=v;
    w[tot]=v;
}
int s,t;
int d[N],now[N];
queue<int> q;
int bfs()
{
    memset(d,0,sizeof(d));
    while(q.size()) q.pop();
    d[s]=1;
    now[s]=head[s];
    q.push(s);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=next1[i])
        {
            int v=to[i];
            if(!val[i]||d[v]) continue;
            d[v]=d[x]+1;
            now[v]=head[v];
            if(v==t) return 1;
            q.push(v);
        }
    }
    return 0;
}
double dinic(int x,double flow)
{
    if(x==t) return flow;
    double res=0;
    for(int i=now[x];i;i=next1[i])
    {
        now[x]=i;
        int v=to[i];
        if(!val[i]||d[v]!=d[x]+1) continue;
        double k=dinic(v,min(val[i],flow-res));
        if(fabs(k)<eps) d[v]=0;
        val[i]-=k;
        val[i^1]+=k;
        res+=k;
        if(res>=flow) break;
    }
    return res;
}
double check(double x)
{
    double res=0;
    for(int i=2;i<=tot;i+=2)
    if(w[i]-x<=0)
    {
        res+=w[i]-x;
        val[i]=val[i^1]=0;
    }
    else
    val[i]=val[i^1]=w[i]-x;
    double ans=0,flow;
    while(bfs())
    while(flow=dinic(s,1e7)) ans+=flow;
    return ans+res;
}
int main()
{
    int n,m;
    cin>>n>>m>>s>>t;
    int x,y;
    double v;
    while(m--)
    {
        scanf("%d %d",&x,&y);
        cin>>v;
        lian(x,y,v);
        lian(y,x,v);
    }
    double l=0,r=1e7;
    while(r-l>eps)
    {
        double mid=(l+r)/2;
        if(check(mid)<0) r=mid;
        else
        l=mid;
    }
    printf("%.2f",r);
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



小树苗
2020-09-25 16:54
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
const int N=1000+5;
const int M=500*500/2+500*2+5;
const int inf=0x3f3f3f3f;
int tot=1;
int head[N],to[M*2],next1[M*2],val[M*2];
void lian(int x,int y,int v)
{
    to[++tot]=y;
    next1[tot]=head[x];
    head[x]=tot;
    val[tot]=v;
}
int s,t;
int a[N],f[N];
int d[N],now[N];
queue<int> q;
int bfs()
{
    memset(d,0,sizeof(d));
    while(q.size()) q.pop();
    d[s]=1;
    now[s]=head[s];
    q.push(s);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=next1[i])
        {
            int v=to[i];
            if(!val[i]||d[v]) continue;
            d[v]=d[x]+1;
            now[v]=head[v];
            if(v==t) return 1;
            q.push(v);
        }

    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t) return flow;
    int res=0;
    for(int i=now[x];i;i=next1[i])
    {
        now[x]=i;
        int v=to[i];
        if(!val[i]||d[v]!=d[x]+1) continue;
        int k=dinic(v,min(val[i],flow-res));
        if(!k) d[v]=0;
        val[i]-=k;
        val[i^1]+=k;
        res+=k;
        if(res==flow) break;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    s=0,t=n*2+1;
    f[1]=1;
    lian(s,1,1);
    lian(1,s,0);
    for(int i=1;i<=n;i++)
    {
        lian(i,i+n,1);
        lian(i+n,i,0);
    }
    for(int i=2;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<=i-1;j++)
        if(a[j]<=a[i])
        f[i]=max(f[i],f[j]+1);
        if(f[i]!=1)
        {
            for(int j=1;j<=i-1;j++)
            if(a[j]<=a[i]&&f[j]==f[i]-1) {
                lian(j+n,i,1);
                lian(i,j+n,0);
            }
        }
        else
        {
            lian(s,i,1);
            lian(i,s,0);
        }
    }
    int len=0;
    for(int i=1;i<=n;i++)
    len=max(len,f[i]);
    cout<<len<<endl;
    int bz=0;
    for(int i=1;i<=n;i++)
    if(f[i]==len)
    {
        lian(i+n,t,1);
        if(i==n)
        bz=tot;
        lian(t,i+n,0);

    }
    int ans=0,flow;
    while(bfs())
    while(flow=dinic(s,inf)) ans+=flow;
    cout<<ans<<endl;
    for(int i=2;i<=tot;i+=2)
    {
        int a=to[i^1],b=to[i];
        if(a==1&&b==n+1) val[i]=inf;
        if(a==s&&b==1) val[i]=inf;
        if(a==n&&b==n+n) val[i]=inf;
        if(a==n+n&&b==t) val[i]=inf;
    }
    if(n==1)
    {
        cout<<"1"<<endl;
    }
    else
    {
    while(bfs())
    while(flow=dinic(s,inf)) ans+=flow;
    cout<<ans;    
    }

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~