头像

Overnoise

ZTOI




离线:8小时前



最大流模板

#include<bits/stdc++.h>
using namespace std;
const int N=20005,M=200005,INF=100000;
int n,m,S,T;
struct oppo{
    int to,nex,s;
}rod[M];
int head[N],tot;
void add(int from,int to,int s)
{
    rod[tot].to=to;
    rod[tot].nex=head[from];
    rod[tot].s=s;
    head[from]=tot++;
}
void link(int from,int to,int s)
{
    add(from,to,s);
    add(to,from,0);
}
int cur[N],d[N];
bool bfs()
{
    queue< int > v;
    memset(d,-1,sizeof(d));
    d[S]=0,cur[S]=head[S];
    v.push(S);
    while(v.size())
    {
        int lxl=v.front();
        v.pop();
        for(int i=head[lxl];~i;i=rod[i].nex)
        {
            int to=rod[i].to;
            if(rod[i].s&&d[to]==-1){
                d[to]=d[lxl]+1;
                cur[to]=head[to];
                if(to==T) return 1;
                v.push(to);
            }
        }
    }
    return 0;
}
int find(int x,int low)
{
    if(x==T) return low;
    int all=0;
    for(int i=cur[x];~i;i=rod[i].nex)
    {
        cur[x]=i;
        int to=rod[i].to;
        if(d[to]==d[x]+1&&rod[i].s)
        {
            int t=find(to,min(rod[i].s,low-all));
            if(!t) d[to]=-1;
            rod[i].s-=t;
            rod[i^1].s+=t;
            all+=t;
        }
        if(all==low) break;
    }
    return all;
}
int dinic()
{
    int ans=0,r;
    while(bfs()) while(r=find(S,INF)) ans+=r;
    return ans;
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m>>S>>T;
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        link(a,b,c);
    }
    cout<<dinic()<<"\n";
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
const int N=305,M=200005,INF=1000005;
int m,n,S,T;
struct oppo{
    int to,nex,s;
}rod[M];
int head[N],tot;
void add(int from,int to,int s)
{
    rod[tot].to=to;
    rod[tot].s=s;
    rod[tot].nex=head[from];
    head[from]=tot++;
}
void link(int from,int to,int s)
{
    add(from,to,s);
    add(to,from,0);
}
int d[N],cur[N];
bool bfs()
{
    queue<int> v;
    memset(d,-1,sizeof(d));
    d[S]=0;cur[S]=head[S];v.push(S);
    while(v.size())
    {
        int lxl=v.front();
        v.pop();
        for(int i=head[lxl];~i;i=rod[i].nex){
            int to=rod[i].to;
            if(d[to]==-1&&rod[i].s)
            {
                d[to]=d[lxl]+1;
                cur[to]=head[to];
                if(to==T) return 1;
                v.push(to);
            }
        }
    }
    return 0;
}
int find(int x,int low)
{
    if(x==T) return low;
    int all=0;
    for(int i=cur[x];~i;i=rod[i].nex)
    {
        cur[x]=i;
        int to=rod[i].to;
        if(d[to]==d[x]+1&&rod[i].s)
        {
            int t=find(to,min(rod[i].s,low-all));
            if(!t) d[to]=-1;
            rod[i].s-=t;
            rod[i^1].s+=t;
            all+=t;
        }
        if(all==low) break;
    }
    return all;
}
int dinic()
{
    int ans=0,r;
    while(bfs()) while(r=find(S,INF)) ans+=r;
    return ans;
}
int g[N];
int main()
{
    memset(head,-1,sizeof(head));
    cin>>m>>n;
    S=0,T=m+n+1;
    for(int i=1;i<=m;i++){
        int a;
        scanf("%d",&a);
        link(S,i,a);
        g[i]=i;
    }
    for(int i=1;i<=n;i++){
        int a,k;
        scanf("%d",&a);
        for(int j=1;j<=a;j++){
            scanf("%d",&k);
            link(g[k],m+i,INF);
            g[k]=m+i;
        }
        scanf("%d",&k);
        link(m+i,T,k);
    }
    cout<<dinic()<<"\n";
    return 0;
}


新鲜事 原文

Overnoise
3个月前
CSP初赛RP++


分享 初赛资料

Overnoise
3个月前

最近在搞NOIP初赛,看了不少博客和资料
这里给大家推荐一些比较好的资料
(如果你们也有好资料,也可以在评论区提出来,大家互相分享嘛)

http://www.doc88.com/p-9982181637642.html
https://www.cnblogs.com/fusiwei/p/11559403.html




Overnoise
4个月前

python 3

a,b=map(int,input().split())
print(a*b-a-b)


问题 acwing bug++

Overnoise
4个月前

@yxc
用火狐浏览器:Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:80.0) Gecko/20100101 Firefox/80.0
看视频
暂停后再播放,有一定几率视频无声音




Overnoise
4个月前

python3

n,k=map(int,input().split())
print('1' if(n%(k+1)!=0) else '2')



Overnoise
4个月前

链接: https://share.weiyun.com/3rS0INLt 密码:e1h4rc




Overnoise
4个月前

链接: https://share.weiyun.com/0TIZ84U3 密码:7gapqj

预览

1.png



分享 欧拉函数

Overnoise
4个月前

转载来自: https://blog.csdn.net/liuzibujian/article/details/81086324
注:这是我见过写得比较好的博客了
2.png

void euler(int n)
{
    for (int i=1;i<=n;i++) phi[i]=i;
    for (int i=2;i<=n;i++)
    {
        if (phi[i]==i)//这代表i是质数
        {
            for (int j=i;j<=n;j+=i)
            {
                phi[j]=phi[j]/i*(i-1);//把i的倍数更新掉
            }
        }
    }
}

1.png

void euler(int n)
{
    phi[1]=1;//1要特判 
    for (int i=2;i<=n;i++)
    {
        if (flag[i]==0)//这代表i是质数 
        {
            prime[++num]=i;
            phi[i]=i-1;
        }
        for (int j=1;j<=num&&prime[j]*i<=n;j++)//经典的欧拉筛写法 
        {
            flag[i*prime[j]]=1;//先把这个合数标记掉 
            if (i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];//若prime[j]是i的质因子,则根据计算公式,i已经包括i*prime[j]的所有质因子 
                break;//经典欧拉筛的核心语句,这样能保证每个数只会被自己最小的因子筛掉一次 
            }
            else phi[i*prime[j]]=phi[i]*phi[prime[j]];//利用了欧拉函数是个积性函数的性质 
        }
    }
}