首页 > 其他分享 >模板库

模板库

时间：2024-09-14 17:03:22浏览次数：12  
标签：return vis int long fa 模板 dis

数据结构

莫队

普通莫队

题目来源：P1494 [国家集训队] 小 Z 的袜子。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
struct node
{
    int l, r, id;
} q[N];
struct node2
{
    int c, s;
} ans[N];
int n, m;
int a[N], st[N], ed[N], vis[N], be[N];
int sum;
bool cmp(node x, node y)
{
    if (be[x.l] == be[y.l])
        return be[x.r] == be[x.r] ? (x.r < y.r) : (be[x.r] < be[y.r]);
    return be[x.l] < be[y.l];
}
void ins(int x)
{
    sum += (2 * vis[a[x]]);
    vis[a[x]]++;
}
void de(int x)
{
    sum = sum - 2 * vis[a[x]] + 2;
    vis[a[x]]--;
}
long long gcdd(long long a, long long b)
{
    return b != 0 ? gcdd(b, a % b) : a;
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> q[i].l >> q[i].r, q[i].id = i;
    int t = sqrt(m);
    for (int i = 1; i <= t; i++)
        st[i] = (i - 1) * t + 1, ed[i] = i * t;
    if (m > ed[t])
        t++, st[t] = ed[t - 1] + 1, ed[t] = n;
    for (int i = 1; i <= t; i++)
        for (int j = st[i]; j <= ed[i]; j++)
            be[j] = i;
    sort(q + 1, q + 1 + m, cmp);
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++)
    {
        if (q[i].l == q[i].r)
        {
            ans[q[i].id] = {1, 0};
            continue;
        }
        while (l > q[i].l)
            ins(--l);
        while (r < q[i].r)
            ins(++r);
        while (l < q[i].l)
            de(l++);
        while (r > q[i].r)
            de(r--);
        long long x = (r - l + 1) * (r - l);
        long long y = sum;
        long long z = gcdd(x, sum);
        ans[q[i].id].c = x / z;
        ans[q[i].id].s = y / z;
    }
    for (int i = 1; i <= m; i++)
    {
        printf("%d/%d\n", ans[i].s, ans[i].c);
    }
    return 0;
}

树上莫队

问题求解树上两个节点 \(u,v\) 最短路径上节点的权值中位数。

算法：莫队加分块。

把树变成括号序，记录 \(dfn[i]\)，\(id[0][i],id[1][i]\)，表示括号序，括号序的映射。

询问分两种情况：

先保持：\(id[1][u]<=id[1][v]\)，为了使 \(u\) 在 \(v\) 前面。

  1. \(u,v\) 在两个子树内，\(q[i]={id[1][u],id[0][v],i}\)，先上去（从 \(u\) 回溯开始）再下去（到 \(v\) 搜索开始）。

  2. \(u,v\) 在一个子树内，\(q[i]={id[0][v]+1,id[0][u],i}\)，\(u\) 在 \(v\) 中，从 \(v\) 走到 \(u\)。

莫队移动 \(l,r\) 时，如果 \(u\) 在不在 \(l,r\) 中，就执行原来的操作，如果不在就执行相反的。

void upd(int u,int op)
{
	(usd[u]&1)?del(u):ins(u);	
	usd[u]+=op?1:-1;
}

code:

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=2e5+10;
int las[N],to[N],nxt[N],cnt,c[N],id[2][N],a[N];
int dfn[N],tot,col[N],usd[N],ss;
double ans[N];
int n,mm,maxx;
struct node2
{
	int l,r,id;
}q[N];
struct node
{
	int l[N],r[N],sum[N],len,m,be[N],B;
	void clear()
	{
		memset(sum,0,sizeof sum);
	}
	void init()
	{
		B=sqrt(len);
		m=len/B;
		for(int i=1;i<=m;i++)
			l[i]=(i-1)*B+1,r[i]=i*B;
		if(r[m]<len)
			l[m+1]=r[m]+1,r[++m]=len;
		for(int i=1;i<=m;i++)
			for(int j=l[i];j<=r[i];j++)	be[j]=i;
	}
}t,mid;
void add(int u,int v,int w)
{
	nxt[++cnt]=las[u];
	las[u]=cnt;
	to[cnt]=v;
	c[cnt]=w;
}
bool cmp(node2 a,node2 b)
{
	int la=a.l,lb=b.l,ra=a.r,rb=b.r;
	if(t.be[la]!=t.be[lb])return t.be[la]<t.be[lb];
	return ra<rb;	
}
void dfs(int u,int fa)
{
	dfn[++tot]=u;
	id[0][u]=tot;
	for(int e=las[u];e;e=nxt[e])
	{
		int v=to[e];
		if(v==fa)	continue;
		a[v]=c[e];
		dfs(v,u);
	}
	dfn[++tot]=u;
	id[1][u]=tot;
}
void ins(int x)
{
	x=a[x];
	col[x]++;
	mid.sum[mid.be[x]]++;
	ss++;
}
void del(int x)
{
	x=a[x];
	col[x]--;
	mid.sum[mid.be[x]]--;
	ss--;
}
void upd(int u,int op)
{
	(usd[u]&1)?del(u):ins(u);	
	usd[u]+=op?1:-1;
}
int get(int x)
{
	int now=0;
	for(int i=1;i<=mid.m;i++)
		if(mid.sum[i]+now>=x)
		{
			for(int j=mid.l[i];j<=mid.r[i];j++)
				if(now+col[j]>=x)	return j;
				else now+=col[j];
		}
		else now+=mid.sum[i];
			
}
void sovle()
{
	memset(las,0,sizeof las);
	memset(col,0,sizeof col);
	memset(usd,0,sizeof usd);
	t.clear(),mid.clear();
	cnt=ss=tot=0;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w),add(v,u,w);
		maxx=max(maxx,w);
	}
	dfs(1,0);
	t.len=tot,mid.len=maxx;
	t.init(),mid.init();
	scanf("%d",&mm);
	for(int i=1;i<=mm;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if(id[1][u]>id[1][v])	swap(u,v);
		if(id[0][u]<id[0][v])	q[i]={id[1][u],id[0][v],i};
		else q[i]={id[0][v]+1,id[0][u],i};
	}
	sort(q+1,q+1+mm,cmp);
	int l=1,r=0;
	for(int i=1;i<=mm;i++)
	{
		//cout<<q[i].l<<" "<<q[i].r<<endl;
		while(l>q[i].l)	upd(dfn[--l],1);
		while(r<q[i].r)	upd(dfn[++r],1);
		while(l<q[i].l)	upd(dfn[l++],0);
		while(r>q[i].r)	upd(dfn[r--],0);
		//cout<<ss<<endl;
		//for(int i=1;i<=maxx;i++)	cout<<col[i]<<" ";	cout<<endl;
		ans[q[i].id]=ss&1?get((ss+1)/2):(get(ss/2+1)+get(ss/2))/2.0;
		//cout<<"ans"<<ans[q[i].id]<<endl;
	}
	for(int i=1;i<=mm;i++)	printf("%.1lf\n",ans[i]);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)	sovle();
	return 0;
 } 
 /*
多测的数据
2
6
1 2 9
2 5 5
2 4 7
3 5 1
3 6 4
3
1 3
4 6
2 6
6
1 2 9
2 5 5
2 4 7
3 5 1
3 6 4
3
1 3
4 6
2 6
 */

图论

树的基本知识

树的重心

没有模板题，用的会议这道题。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
vector<int>e[N];
int n;
int siz[N],res,d[N],f[N];
void dfs(int u,int fa)
{
    siz[u]=1;
    mx=0;
    for(auto v : e[u])
    {
        if(v==fa)   continue;
        dfs(v,u);
        siz[u]+=siz[v];
        f[u]=max(siz[v],f[u]);
    }
    f[u]=max(n-siz[u],f[u]);
    if(f[u]<f[res]||(f[u]==f[res]&&res>u))    
        res=u;
}
void dfs2(int u,int fa)
{
    
    for(auto v : e[u])
    {
        if(v==fa)   continue;
        d[v]=d[u]+1;
        dfs2(v,u);
        
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    f[0]=1e9+10;
    dfs(1,0);
    dfs2(res,0);
    for(int i=1;i<=n;i++)
        ans+=d[i];
    printf("%d %d",res,ans);
}

重链剖分

两次搜索预处理。

void dfs1(int u,int fa)
{
    f[u]=fa;
    siz[u]=1;
    dep[u]=dep[fa]+1;
    for(int e=las[u];e;e=nxt[e])
    {
        int v=to[e];
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])  son[u]=v; 
    }
}
void dfs2(int u,int tp_now)
{
    id[0][u]=++tim;
    dfn[tim]=u;
    tp[u]=tp_now;
    if(son[u]) 
        dfs2(son[u],tp_now);
    for(int e=las[u];e;e=nxt[e])
    {
        int v=to[e];
        if(son[u]==v||v==f[u])   continue;
        dfs2(v,v);
    }
    id[1][u]=tim;
}

线段树区间操作时的跳链：

void upchange(int u,int v,int x)
{
//	cout<<"#####"<<endl;
    while(top[u]!=top[v])
    {
        if(dep[tp[u]]<dep[tp[v]])swap(u,v);
        change(1, id[0][tp[u]], id[0][u], x);
        u=f[tp[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    change(1, id[0][u], id[0][v], x);
        
}
int upask(int u,int v)
{
    int res=0;
    while(tp[u]!=tp[v])
    {
        if(dep[tp[u]]<dep[tp[v]])swap(u,v);
        res+=ask(1, id[0][tp[u]], id[0][u]);
        res%=mod;
        u=f[tp[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    res+=ask(1, id[0][u], id[0][v]);
    return res%mod;
}

最短路

Floyd

#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 10, inf = 1e9 + 10;
int n, m;
int dis[N][N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j)
                dis[i][j] = inf;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        dis[u][v] = dis[v][u] = min(dis[u][v], w);
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            printf("%d ", dis[i][j]);
        puts("");
    }
    return 0;
}

dijstra

#include <bits/stdc++.h>
#define pii pair<long long, int>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int n, m, s;
ll dis[N];
bool vis[N];
vector<pii> e[N];
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    priority_queue<pii, vector<pii>, greater<pii>> q;
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto t : e[u])
        {
            int v = t.first, w = t.second;
            if (dis[v] > dis[u] + w)
                dis[v] = dis[u] + w, q.push({dis[v], v});
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%lld ", dis[i]);
    return 0;
}

johnson

#include<bits/stdc++.h>
#define pii pair<int,int>
typedef long long ll;
using namespace std;
const int N=3e3+10,M=6e3+10;
const ll inf=1e18;
int n,m,num[N];
vector<pii>e[N];
ll dis[N],d[N];
bool vis[N];
bool spfa(int s)
{
    fill(dis,dis+n+1,inf);
    dis[s]=0,vis[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto t : e[u])
        {
            int v=t.first,w=t.second;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                    num[v]++;
                    if(num[v]==n+1)
                        return 0;
                }
            }
        }
    }
    return 1;
}
void dij(int s)
{
    fill(d,d+1+n,inf);
    fill(vis,vis+1+n,0);
    d[s]=0;
    priority_queue<pii,vector<pii>,greater<pii> >q;
    q.push({0,s});
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u])  continue;
        vis[u]=1;
        for(auto t : e[u])
        {
            int v=t.first,w=t.second;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push({d[v],v});
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[u].push_back({v,w});
    }
    for(int i=1;i<=n;i++)
        e[n+1].push_back({i,0});
    if(!spfa(n+1))
        return puts("-1"),0;
    for(int i=1;i<=n;i++)
        for(auto &t: e[i])
            t.second+=dis[i]-dis[t.first];
    for(int i=1;i<=n;i++)
    {
        dij(i);
        ll ans=0;
        for(int j=1;j<=n;j++)
            if(d[j]==inf) ans+=1ll*1e9*j;
            else ans+=(d[j]+dis[j]-dis[i])*j;
        printf("%lld\n",ans);
    }
    return 0;
}

连通性问题

割点

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>e[N];
int n,m;
int dfn[N],low[N],buc[N],tim;
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++tim;
    int son=0;
    for(auto v : e[u])
    {
        if(v==fa)   continue;
        if(!dfn[v])
        {
            son++,tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]&&fa!=0)   buc[u]=1;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(son>=2&&fa==0)   buc[u]=1;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v),e[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) tarjan(i,0);
    }
    int ans=0;
    for(int i=1;i<=n;i++)   ans+=buc[i];
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
        if(buc[i])  printf("%d ",i);
    return 0;
}

割边

code:

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=1e6+10;
int n,m;
vector<pii>e[N];
int tim,dfn[N],stk[N],top,low[N],tot;
vector<int>ans[N];
void form(int u)
{
    ++tot;
    do{ans[tot].push_back(stk[top]);}
    while(stk[top--]!=u);
}
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++tim;
    stk[++top]=u;
    for(auto t : e[u])
    {
        if(t.second==fa)    continue;
        int v=t.first;
        if(!dfn[v])
        {
            tarjan(v,t.second);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v])   form(v);
        }
        else low[u]=min(low[u],dfn[v]);
    }   
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back({v,i}),e[v].push_back({u,i});
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i,0),form(i);
    printf("%d\n",tot);
    for(int i=1;i<=tot;i++)
    {
        printf("%d ",ans[i].size());
        for(auto v : ans[i])    printf("%d ",v);
        puts("");
    }
    return 0;
}

树上相关

最近公共祖先

倍增法(O(nlogn)-O(logn)):

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
struct getlca
{
    int las[N],to[N],cut,nxt[N],c[N];
    
    int dep[N],f[N][20];
    void add(int u,int v)
    {
        cut++;
        nxt[cut]=las[u];
        las[u]=cut;
        to[cut]=v;
    }
    void init(int u,int fa)
    {
        dep[u]=dep[fa]+1;
        f[u][0]=fa;
        for(int i=1;i<=19;i++)
        f[u][i]=f[f[u][i-1]][i-1];
        for(int e=las[u];e;e=nxt[e])
        {
            int v=to[e];
            if(fa==v)continue;
            init(v,u);
        }
    }
    int lca(int u,int v)
    {
        if(dep[u]<dep[v])swap(u,v);
        for(int i=19;i>=0;i--)
        if(dep[u]-(1<<i)>=dep[v])u=f[u][i];
        if(v==u) return u;
        for(int i=19;i>=0;i--)
        {
            if(f[u][i]!=f[v][i])
            u=f[u][i],v=f[v][i];
        }
        return f[u][0];
    }
}T;
int n,m,st;
int main()
{
	cin>>n>>m>>st;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		T.add(u,v),T.add(v,u);
	}
	T.init(st,0);
	while(m--)
	{
		int u,v;
		cin>>u>>v;
		cout<<T.lca(u,v)<<endl;
	}
	return 0;
}

tarjan(离线)(O(n)-O(n)):

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=5e5+10;
int n,m,s;
vector<int>e[N];
vector<pii>q[N];
int fa[N],dep[N],ans[N];
bool vis[N];
int find(int x)
{
    if(x==fa[x])    return x;
    return fa[x]=find(fa[x]);
}
void uni(int x,int y)
{
    x=find(x),y=find(y);
    if(dep[x]>dep[y])   fa[x]=y;
    else fa[y]=x;
}
void tarjan(int u,int fa)
{
    dep[u]=dep[fa]+1;
    vis[u]=1;
    for(auto v : e[u])
    {
        if(v==fa)   continue;
        tarjan(v,u);
        uni(u,v);
    }
    for(auto t : q[u])
        if(vis[t.first])    ans[t.second]=find(t.first);
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++)   fa[i]=i;
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        q[u].push_back({v,i});
        q[v].push_back({u,i});
    }
    tarjan(s,0);
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

dfs 序 + st 表(O(nlogn)-O(1)):

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>e[N];
int n,m,s;
struct getlca
{
    int f[20][N],tot=0,dfn[N];
    void init(int u,int fa)
    {
        dfn[u]=++tot;
        f[0][tot]=fa;
        for(auto v : e[u])
        {
            if(v==fa)   continue;
            init(v,u);
        }
    }
    int get(int u,int v){return dfn[u]<dfn[v]?u:v;}
    int lca(int u,int v)
    {
        if(u==v)    return u;
        if(dfn[u]>dfn[v])   swap(u,v);
        u=dfn[u]+1,v=dfn[v];
        int t=log2(v-u+1);
        return get(f[t][u],f[t][v-(1<<t)+1]);
    }
}T;
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    T.init(s,0);
    for(int i=1;i<=19;i++)
        for(int j=1;j<=n;j++)
            T.f[i][j]=T.get(T.f[i-1][j],T.f[i-1][j+(1<<i-1)]);
    while(m--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%d\n",T.lca(u,v));
    }
    return 0;
}

网络流

最大流

dinic 算法。

#include<bits/stdc++.h>
using namespace std;
const int N=200+10,M=5e3+10;
int n,m,S,T;
struct dinic
{
    int las[N],to[M<<1],nxt[M<<1],lim[M<<1],cnt=1;
    void add(int u,int v,int li)
    {
        nxt[++cnt]=las[u];
        las[u]=cnt;
        to[cnt]=v;
        lim[cnt]=li;
    }
    int cur[N],dis[N],fr[N],fl[N];
    long long dfs(int u,long long res)
    {
        if(u==T)    return res;
        long long flow=0;
        for(int i=las[u];i&&res;i=nxt[i])
        {
            cur[u]=i;
            int c=min((long long)lim[i],res),v=to[i];
            if(dis[v]==dis[u]+1&&c)
            {
                int k=dfs(v,c);
                flow+=k,lim[i]-=k,lim[i^1]+=k,res-=k;
            }
        }
        if(!flow)   dis[u]=-1;
        return flow;
    }
    long long maxflow(int s,int t)
    {
        long long flow=0;
        while(1)
        {
            memcpy(cur,las,sizeof las);
            memset(dis,-1,sizeof dis);
            queue<int>q;
            q.push(s);
            dis[s]=0;
            while(!q.empty())
            {
                int u=q.front();q.pop();
                for(int i=las[u];i;i=nxt[i])
                {
                    int v=to[i];
                    if(lim[i]&&dis[v]==-1)
                    {
                        dis[v]=dis[u]+1;
                        q.push(v);
                    }
                }
            }
            if(dis[t]==-1)  return flow;
            flow+=dfs(s,1e18);
        }
    }
}G;
int main()
{
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i=1;i<=m;i++)
    {
        int u,v,li;
        scanf("%d%d%d",&u,&v,&li);
        G.add(u,v,li),G.add(v,u,0);
    }
    printf("%lld",G.maxflow(S,T));
    return 0;
}

最小费用最大流

SSP 算法。

注意点：

  1. 链式前向星的 cnt 一定从 \(1\) 开始，因为要成对变换。

  2. 每增广路一次就要初始化。

  3. SPFA 在队首为 \(T\) 时不能直接 break，因为第一次取出 \(T\) 时 \(dis[T]\) 不一定取到最短路。

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=5e3+10,M=5e4+10;
int n,m,S,T;
struct SSP
{
    int las[N],nxt[M<<1],to[M<<1],c[M<<1],lim[M<<1],cnt=1;
    void add(int u,int v,int w,int li)
    {
        nxt[++cnt]=las[u];
        las[u]=cnt;
        to[cnt]=v;
        c[cnt]=w;
        lim[cnt]=li;
    }
    int fl[N],fr[N],vis[N],dis[N];
    pii mincost(int s,int t)
    {
        int flow=0,cost=0;
        while(1)
        {
            memset(dis,0x3f,sizeof dis);
            memset(vis,0,sizeof vis);
            dis[s]=0,fl[s]=1e9;
            queue<int>q;
            q.push(s);
            vis[s]=1;
            while(!q.empty())
            {
                int u=q.front();q.pop();
                vis[u]=0;
                for(int i=las[u];i;i=nxt[i])
                {
                    int v=to[i];
                    if(dis[v]>dis[u]+c[i]&&lim[i])
                    {
                        dis[v]=dis[u]+c[i];
                        fr[v]=i;
                        fl[v]=min(fl[u],lim[i]);
                        if(!vis[v]) vis[v]=1,q.push(v);
                    }
                }
            }            
            if(dis[t]>1e9)  return {flow,cost};
            flow+=fl[t],cost+=fl[t]*dis[t];
            for(int u=t;u!=s;u=to[fr[u]^1])
                lim[fr[u]]-=fl[t],lim[fr[u]^1]+=fl[t];
        }
    }
    
}G;
int main()
{
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i=1;i<=m;i++)
    {
        int u,v,w,li;
        scanf("%d%d%d%d",&u,&v,&li,&w);
        G.add(u,v,w,li),G.add(v,u,-w,0);
    }
    auto ans=G.mincost(S,T);
    printf("%d %d",ans.first,ans.second);
    return 0;
}

数学

矩阵相关

高斯消元

以SDOI2006 线性方程组为模板。

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
double a[110][110];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            cin>>a[i][j];
    int r=1;
    for(int i=1;i<=n;i++)
    {
        int t=r;
        for(int j=r+1;j<=n;j++)
            if(fabs(a[j][i])>fabs(a[t][i])) t=j;
        if(fabs(a[t][i])<eps)   continue;
        for(int j=i;j<=n+1;j++)  
            swap(a[r][j],a[t][j]);
        for(int j=n+1;j>=i;j--)
            a[r][j]/=a[r][i];
        for(int j=r+1;j<=n;j++)
            for(int z=n+1;z>=i;z--)
                a[j][z]-=a[j][i]*a[r][z];
        r++;
    }
    if(r<=n)
    {
        for(int i=r;i<=n+1;i++)
            if(fabs(a[i][n+1])>eps)
                return puts("-1"),0;
        return puts("0"),0;
    }
    for(int i=n-1;i>=1;i--)
        for(int j=i+1;j<=n;j++)
            a[i][n+1]-=a[j][n+1]*a[i][j];
    for(int i=1;i<=n;i++)
        printf("x%d=%.2lf\n",i,a[i][n+1]);
    return 0;
}

同余相关

扩展中国剩余定理

#include<bits/stdc++.h>
using namespace std;
typedef __int128_t ll;
const int N=1e7+10;
ll gcd(ll aa,ll bb)
{
    if(!bb) return aa;
    return gcd(bb,aa%bb);
}
ll lcm(ll aa,ll bb)
{
    return aa/gcd(aa,bb)*bb;
}
ll exgcd(ll aa,ll bb,ll &x,ll &y)
{
    if(!bb)
    {
        x=1,y=1;
        return aa;
    }
    ll d=exgcd(bb,aa%bb,x,y);
    ll z=x;
    x=y;
    y=z-(aa/bb)*y;
    return d;
}
long long a[N],b[N],n;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i],&b[i]);
    ll a1=a[1],b1=b[1];
    for(int i=2;i<=n;i++)
    {
        ll a2=a[i],b2=b[i],x,y;
        ll c=b2-b1;
        ll d=exgcd(a1,a2,x,y);
        if(c%d)
            return puts("-1"),0;
        c/=d;
        x=x*c%(a2/d);
        if(x<0) x+=(a2/d);
        ll mod=lcm(a1,a2);
        b1=(a1*x+b1)%mod;
        if(b1<mod)  b1+=mod;
        a1=mod;
          //printf("a b %lld %lld\n",(long long)a1,(long long)b1);
    }
    printf("%lld",(long long)((b1%a1)+a1)%a1);
    return 0;
}

标签：return,vis,int,long,fa,模板,dis
From： https://www.cnblogs.com/hutongzhou/p/18327934

相关文章

  • template<> 模板特化
    template<>是用于模板特化（TemplateSpecialization）的一种语法。模板特化允许你为某些特定的模板参数提供不同的实现。例如，template<>structFac<0>是一个对Fac模板类的完全特化，它专门处理模板参数为0的情况template<>structFac<0>{conststaticintvalue=1;}......
  • 模板声明的两种形式：template<int N> 和 template<N>
    template<intN>：非类型模板参数template<intN>是一个典型的非类型模板参数的例子。这里的N是模板的参数，但它不是一个类型，而是一个具体的整数值。这意味着，当你实例化模板时，你必须为N提供一个常量整数值。示例：template<intN>structArray{intdata[N];//创建一......
  • 可筛选的课程表设计excel表格@在线写作共享表格课程表设计模板参考
    文章目录abstract表格任务1.时间段与课次安排2.课程种类多样3.教师与教室安排4.课程颜色编码5.课表标注参考方案:样式预览全表添加不影响筛选列的跨列显示内容方案1方案2(pass)针对指定老师筛选并生成课表......
  • PbootCMS设置当前站点模板,模板子目录,黑白名单,敏感词过滤
    在PBootCMS中，后台操作涉及多个配置项，包括更换模板路径、配置后台模板子目录、配置后台黑名单和白名单以及敏感词过滤。下面是详细的步骤和说明。1.更换模板路径步骤进入站点信息页面：登录PBootCMS后台。导航至 【基础内容】-【站点信息】-【站点模板】。选择模板......
  • 208. 实现 Trie (前缀树)||Trie字典树模板
    题目：https://leetcode.cn/problems/implement-trie-prefix-tree/description/以前的板子写得太丑陋了，重新写一份><因为是leetcode上的题目，所以是核心代码模式。字典树（Trie）原理：（因为我语言表达能力不行，所以以下内容来源于小美AI机器人><）字典树（Trie）是一种用于高效存储和检索字......
  • PbootCMS模板中那些url怎么调用
    在PBootCMS中，httpurl、pageurl 和 sitedomain 标签用于获取当前站点的相关网址信息。以下是详细的使用说明和示例代码。1.当前站点网址标签说明{pboot:httpurl}：自适应获取当前访问网址，主要用于需要使用网站路径前缀的情况。示例输出plaintext https://www.xxx.......
  • PbootCMS模板自动生成当前页面二维码
    在PBootCMS中，qrcode 标签用于生成对应文本的二维码图片。这对于产品列表页或详情页为每个产品生成二维码非常有用。以下是详细的使用说明和示例代码。1. qrcode 标签的基本用法参数说明string=*：指定生成二维码的文本内容。2.示例代码生成产品详情页的二维码假设你需......
  • 怎么安装使用PbootCMS网站模板
    安装和使用PBootCMS网站模板的过程主要包括以下几个步骤：1.下载模板访问PBootCMS官网或其他可信来源下载你所需的模板文件。确认下载的模板兼容你的PBootCMS版本。2.上传模板将下载好的模板文件上传到你的服务器或虚拟主机。通常模板文件会被压缩，上传之后需要解压到正确......
  • pbootcms模板时间格式调用方法详解
    在PBootCMS中，时间调用主要通过date标签来实现。以下是一些常用的调用方法及其效果示例：列表页时间调用默认格式：[list:date]效果：2021-12-0609:12:30年月日格式：[list:datestyle=Y-m-d]效果：2021-12-06年格式：[list:datestyle=Y]效果：2021月日格式：[list:da......
  • 基于Uni-app前端框架的SUMER UI3.0组件库！一端开发，多端运行！本组件库可快速二次开发各种
    基于Uni-app前端框架的SUMERUI3.0组件库！一端开发，多端运行！本组件库可快速二次开发各种类别各行业模板，包括：商城、视频、直播、聊天、支付、新闻、社区、地图、导航、出行、社区、博客等sumer-ui介绍基于uView微信小程序UI组件库，兼容vue3。本插件是SUMER组件库，只提供组件......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99