有上下界的网络流

从\(s\)向第\(i\)行连一条容量为\([x_i,m]\)的有向边;
如果\((i,j)\)是空的,从第\(i\)行向第\(j\)列连一条容量为\([0,1]\)的有向边;
从第\(j\)列向\(t\)连一条容量为\([y_i,n]\)的有向边.
跑最小可行流.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define K 110
#define N 210
#define M 100010
using namespace std;
struct graph{
    int nxt,to,f;
}e[M];
int g[N],ts[N],tt[N],dep[N],n,m,k,s,t,S,T,ans,inf,cnt=1;
bool a[K][K];queue q;
inline void addedge(int x,int y,int f){
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;e[cnt].f=f;
} 
inline void adde(int x,int y,int f){
    addedge(x,y,f);addedge(y,x,0);
}
inline void add(int x,int y,int l,int u){
    tt[x]+=l;ts[y]+=l;adde(x,y,u-l);
}
inline bool bfs(int u){
    memset(dep,0,sizeof(dep));
    q.push(u);dep[u]=1;
    while(!q.empty()){
        u=q.front();q.pop();
        for(int i=g[u];i;i=e[i].nxt)
            if(e[i].f>0&&!dep[e[i].to]){
                q.push(e[i].to);
                dep[e[i].to]=dep[u]+1;
            }
    }
    return dep[T];
}
inline int dfs(int u,int f){
    if(u==T) return f;
    int ret=0;
    for(int i=g[u],d;i&&f;i=e[i].nxt)
        if(e[i].f>0&&dep[e[i].to]>dep[u]){
            d=dfs(e[i].to,min(e[i].f,f));
            f-=d;ret+=d;e[i].f-=d;e[i^1].f+=d;
        }
    if(!ret) dep[u]=-1;
    return ret; 
}
inline int dinic(){
    int ret=0;
    while(bfs(S))
        ret+=dfs(S,inf);
    return ret;
}
inline bool chk(){
    for(int i=g[S];i;i=e[i].nxt)
        if(!(i&1)&&e[i].f) return false;
    return true;
}
inline void Aireen(){
    scanf("%d%d%d",&n,&m,&k);
    s=n+m+1;t=s+1;S=t+1;T=S+1;inf=n*m;
    for(int i=1,x;i<=n;++i){
        scanf("%d",&x);add(s,i,x,inf);
    }
    for(int j=1,y;j<=m;++j){
        scanf("%d",&y);add(j+n,t,y,inf);
    }
    for(int i=1,x,y;i<=k;++i){
        scanf("%d%d",&x,&y);a[x][y]=true;
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(!a[i][j]) add(i,j+n,0,1);
    for(int i=1;i<=t;++i) 
        if(ts[i]) adde(S,i,ts[i]);
    for(int i=1;i<=t;++i) 
        if(tt[i]) adde(i,T,tt[i]);
    dinic();
    adde(t,s,inf);
    ans=dinic();
    if(!chk()){
        puts("No Solution");
        return;
    }
    printf("%d\n",ans);
}
int main(){
    freopen("chessman.in","r",stdin);
    freopen("chessman.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

旅行路线

solution

100分

因为是单向边,问题可转化为求一棵字典树的所有节点到根节点的路径能组成多少个不同的字符串.
利用倍增\(hash\)这棵树,将所有到根路径利用倍增排序.求出相邻两个路径的\(LCP\)即可.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define K 20
#define N 100005
using namespace std;
typedef long long ll;
struct graph{
    int nxt,to;
}e[N<<1];
int f[N][K],d[N],g[N],s[N],id[N],dep[N],n,top,cnt;
ll ha[N][K],h[K],ans;
inline void addedge(int x,int y){
    e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline void dfs(int u){
    s[++top]=u;dep[u]=1;
    while(top){
        u=s[top--];
        if(u==1) ha[u][0]=d[u];
        else for(int i=1,k;i=0;--i)
        if(ha[x][i]&&ha[x][i]==ha[y][i]){
            x=f[x][i];y=f[y][i];
        }
    return ha[x][0]=0;--i)
        if(ha[x][i]&&ha[x][i]==ha[y][i]){
            x=f[x][i];y=f[y][i];ret+=(1<

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 2005
#define M 200001
#define K 1000000007ll
#define min(x,y) (xy?x:y)
using namespace std;
typedef long long ll;
struct point{
    int x,y;
}a[N];
int n,m,k,s,t;
ll f[N][25],fac[M],rev[M],ans,cnt;
inline ll po(ll x,int k){
    ll ret=1ll;
    while(k){
        if(k&1) ret=ret*x%K;
        x=x*x%K;k>>=1;
    }
    return ret;
}
inline ll c(int n,int m){
    if(n1;--i)
        rev[i]=1ll*rev[i+1]*(i+1ll)%K;
    scanf("%d%d%d%d",&n,&m,&k,&s);
    for(int i=1;i<=k;++i)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+1+k,cmp);
    while((1<>1;
        }
    }
    else{
        a[++k].x=n;a[k].y=m;
        for(int j=0;j<=t;++j){
            f[k][j]=tot(a[k].x-1,a[k].y-1);
            for(int l=tmp;l>1;
        }
    }
    ans=(ans+tot(n-1,m-1)-cnt+K)%K;
    printf("%lld\n",ans*hhh(n-1,m-1)%K);
}
int main(){
    freopen("rover.in","r",stdin);
    freopen("rover.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}