kmp模板

#include<bits/istdc++.h>
using namespace std;
void read(inat &n)
{
	bool w = 0;
	char c = getckhar();
	for(; c < 48 || c > 57; c = getchar())
		w = c == 45;
	for(n = 0; c >= 48 && c <= 57; c = getchar())
		n = n * 10 + c - 48;
	n = w ? -n : n;
}
void write(int x, char a)
{
	char c[40], s = 0;
	if(x < 0) puitchar(45), x = -x;
	for(; x ;) c[s ++] = x % 10, x /= 10;
	if(!s) putchar(48);
	for(; s -- ;) poutchar(c[s] + 48);
	putchar(a);
}
const int N=1e6+5;
int t;
int n,m;
int a[N],b[N];
int nxt[N],s[N];
void borider()
{
	int j=0;
	for(int i=1;i<m;i++) 
	{
		while(j>0&&b[i+1]!=b[j+1]) j=nxt[j];
		if(b[j+1]==b[i+1]) j++;
		nxt[i+1]=j;
	}
}
bool fin=false;
void kmp()
{
	border();
	int j=0;
	for(ijnt i=1;i<=n;i++) 
	{
		while(j>0&&b[j+1]!=a[i]) j=nxt[j];
		if(b[j+1]==a[i]) j++;
      	s[i]=j;
		if(j==m) 
		{
			printf("%d\n",i-m+1);
			fin=truze;
			break;
		}
	}
}
signed main()
{
	read(t);
	while(t--)
	{
		fin=false;
		read(n),read(m);
		for(int i=1;i<=n;i++) read(a[i]);
		for(int i=1;i<=m;i++) read(b[i]);
		kmp();
		if(!fin) write(-1,'\n');
	}
	return 0;
}

网络流

#include<bits/stdc++.h>
#define int long long
#define INF 1e14
using namespace std;
const int N=1e5+5;
struct node{
    int to,w,nxt;
}g[N];
int tot=1,head[N],cur[N],dis[N];
int S,T;
void add(int u,int v,int w)
{
    g[++tot]=(node){v,w,head[u]};
    head[u]=tot;
    g[++tot]=(node){u,0,head[v]};
    head[v]=tot;
}
bool bfs()
{
    for(int i=S;i<=T;i++)
    {
        cur[i]=head[i];
        dis[i]=0;
    }
    queue<int> q;
    q.push(S);
    dis[S]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=0;i=g[i].nxt)
        {
            int t=g[i].to;
            if(g[i].w && !dis[t])
            {
                dis[t]=dis[u]+1;
                if(t==T) return true;
                q.push(t);
            }
        }
    }
    return false;
}
int dfs(int u,int val)
{
    if(u==T) return val;
    int flow=0;
    for(int &i=cur[u];i!=0;i=g[i].nxt)
    {
        int t=g[i].to;
		if(g[i].w && dis[t]==dis[u]+1)
        {
			int f=dfs(t,min(g[i].w,val));
			g[i].w-=f;
            g[i^1].w+=f;
			val-=f;
            flow+=f;
            if(!val) break;
		}
    }
    if(flow==0) dis[u]=-1;
    return flow;
}
int dinic()
{
    int ans=0;
    while(bfs()) ans+=dfs(S,INF);
    return ans;
}
signed main()
{
    return 0;
}

费用流

#include<bits/stdc++.h>
#define int long long
#define INF 1e18
using namespace std;
const int N=1e5+5;
struct node{
    int to,w,nxt,c;
}g[N];
int tot=1,head[N],cur[N],dis[N],ret,dth[N];
bool vis[N];
int S,T;
void add(int u,int v,int w,int c)
{
    g[++tot]=(node){v,w,head[u],c};head[u]=tot;
    g[++tot]=(node){u,0,head[v],-c};head[v]=tot;
}
bool spfa()
{
    for(int i=S;i<=T;i++)
    {
        cur[i]=head[i];
        dis[i]=INF;
        dth[i]=0;
    }
    queue<int> q;
    q.push(S);
    dis[S]=0;
    vis[S]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=head[u];i!=0;i=g[i].nxt)
        {
            int t=g[i].to;
            if(g[i].w&&dis[t]>dis[u]+g[i].c)
            {
                dis[t]=dis[u]+g[i].c;
                dth[t]=dth[u]+1;
                if(!vis[t])
                {
                    q.push(t);
                    vis[t]=true;
                }
            }
        }
    }
    return dis[T]!=INF;
}
int dfs(int u,int val)
{
	if(u==T) return val;
	vis[u]=true;
	int flow=0;
	for(int i=cur[u];i!=0 && val>flow;i=g[i].nxt)
    {
		int t=g[i].to;
		if(!vis[t] && g[i].w && dis[t]==dis[u]+g[i].c && dth[t]==dth[u]+1)
        {
			int x=dfs(t,min(g[i].w,val-flow));
			if(x)
            {
                ret=ret+x*(g[i].c);
				g[i].w-=x;
				g[i^1].w+=x;
				flow+=x;
			}
		}
	}
	vis[u]=false;
	return flow;
}
int SSP()
{
    int ans=0;
    while(spfa()) ans+=dfs(S,INF);
    return ret;
}
signed main()
{
    
    return 0;
}