【bzoj1877】晨跑

题目大意

给出有$n$个点$m$条边的带权图

要求找到最多的(起点到终点)路径数且使总费用尽量少

路径与路径之间不能相交

建图

每个点只能经过一次

拆点，容量为$1$，费用为$0$

每条边有边权，且使得边权和最小

容量为$+∞$,费用为边权

源点和汇点

点$1$和点$n$可以经过多次，因此不用开超级源和超级汇，直接取点$1$和点$n$分别作为源点和汇点

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7fffffff
using namespace std;
inline int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x;
}

int n,m,et=1,s,t,ans1,ans2;
struct edge{int from,to,next,c,w;}e[100500];
int last[500],dis[500],from[500],inq[500];
inline void addedge(int u,int v,int c,int w){
    e[++et]=(edge){u,v,last[u],c,w};last[u]=et;
    e[++et]=(edge){v,u,last[v],0,-w};last[v]=et;
}

inline bool spfa(){
    queue <int> q;
    For(i,1,2*n) dis[i]=inf;
    q.push(1);dis[1]=0;inq[1]=1;
    while (!q.empty()){
        int h=q.front();q.pop();
        goedge(i,h){
            if (e[i].c && dis[h]+e[i].w<dis[e[i].to]){
                dis[e[i].to]=dis[h]+e[i].w;
                from[e[i].to]=i;
                if (!inq[e[i].to]){
                    q.push(e[i].to);
                    inq[e[i].to]=1;
                }
            }

        }
        inq[h]=0;
    }
    return dis[2*n]!=inf;
}
inline void mcf(){
    int x=inf;
    for(int i=from[2*n];i;i=from[e[i].from])
        x=min(x,e[i].c);
    ans1+=x;

    for(int i=from[2*n];i;i=from[e[i].from]){
        ans2+=x*e[i].w;
        e[i].c-=x;
        e[i^1].c+=x;
    }
}

int main(){
    n=read(),m=read();
    For(i,1,n){
        if (i>1 && i<n) addedge(i,i+n,1,0);
        else addedge(i,i+n,inf,0);
    }
    For(i,1,m){
        int u=read(),v=read(),w=read();
        addedge(u+n,v,1,w);
    }
    while (spfa()) mcf();
    printf("%d %d\n",ans1,ans2);
    return 0;
}

【bzoj2424】订货

题目大意

某公司估计市场在第$i$个月对某产品的需求量为$u_i$，已知在第$i$月该产品的订货单价为$d_i$

上个月月底未销完的单位产品要放在仓库要付存贮费用$m$，仓库容量为$S$

问如何安排这$n$个月订购计划，才能使成本最低？

每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费

建图

每个月对某产品的需求量

每个月作为一个点，向汇点连边，容量为需求量，费用为$0$

每个月的订货单价

源点向汇点连边，容量为$+∞$，费用为订货单价

仓库的用处

每个月向下一个月连一条边，容量为仓库容量，费用为存贮费用

源点和汇点

需要另外开两个新点作为源点和汇点

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7fffffff
using namespace std;
inline int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x;
}

int n,m,S,et=1,s,t,ans;
struct edge{int from,to,next,c,w;}e[100500];
int last[100],inq[100],dis[100],from[100];
inline void addedge(int u,int v,int c,int w){
    e[++et]=(edge){u,v,last[u],c,w};last[u]=et;
    e[++et]=(edge){v,u,last[v],0,-w};last[v]=et;
}

inline bool spfa(){
    For(i,s,t) dis[i]=inf;
    queue <int> q;
    q.push(s);inq[s]=1;dis[s]=0;
    while (!q.empty()){
        int h=q.front();q.pop();
        goedge(i,h)
            if (e[i].c && dis[h]+e[i].w<dis[e[i].to]){
                dis[e[i].to]=dis[h]+e[i].w;
                from[e[i].to]=i;
                if (!inq[e[i].to]){
                    q.push(e[i].to);
                    inq[e[i].to]=1;
                }
            }
        inq[h]=0;
    }
    return dis[t]!=inf;
}

inline void mcf(){
    int x=inf;
    for(int i=from[t];i;i=from[e[i].from])
        x=min(x,e[i].c);
    for(int i=from[t];i;i=from[e[i].from]){
        ans+=x*e[i].w;
        e[i].c-=x;
        e[i^1].c+=x;
    }
}

int main(){
    n=read(),m=read(),S=read();
    s=0,t=n+1;
    For(i,1,n) addedge(i,t,read(),0);
    For(i,1,n) addedge(s,i,inf,read());
    For(i,1,n-1) addedge(i,i+1,S,m);
    while (spfa()) mcf();
    printf("%d\n",ans);
    return 0;
}

【bzoj2661】连连看

题目大意

给出一个闭区间$[a,b]$中的全部整数，如果其中某两个数$x,y$（不妨设$x>y$）的平方差$x^2-y^2$是一个完全平方数$z^2$，并且$y$与$z$互质，那么就可以将$x$和$y$连起来并且将它们一起消除，同时得到$x+y$点分数

要求在消除的数对尽可能多的前提下，得到最多的分数

建图

每个整数消除后消失

所有建边的容量为$1$

一起消除后得到分数

拆点，如果$i,j$能够一起消除这样建边

从$i$连到$j'$，费用为$i+j$

从$i'$连到$i$，费用为$i+j$

源点和汇点

需要另外开两个新点作为源点和汇点

从源点向每个点连一条费用为$0$的边，从每个点向汇点连一条费用为$0$的边

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x7fffffff
using namespace std;
inline int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x;
}
inline int sqr(int x){return x*x;}
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

int l,r,ans1,ans2,s=0,t=2001,et=1;
struct edge{int from,to,next,c,w;}e[2000500];
int last[5050],dis[5050],inq[5050],from[5050];
inline void addedge(int u,int v,int c,int w){
    e[++et]=(edge){u,v,last[u],c,w};last[u]=et;
    e[++et]=(edge){v,u,last[v],0,-w};last[v]=et;
}

inline bool judge(int x,int y){
    if (x<y) swap(x,y);
    int z=(int)sqrt(sqr(x)-sqr(y));
    return x*x-y*y==z*z && gcd(y,z)==1;
}

inline bool spfa(){
    For(i,s,t) dis[i]=-inf;
    queue <int> q;
    q.push(s);dis[s]=0;inq[s]=1;
    while (!q.empty()){
        int h=q.front();q.pop();
        goedge(i,h)
            if (e[i].c && dis[h]+e[i].w>dis[e[i].to]){
                dis[e[i].to]=dis[h]+e[i].w;
                from[e[i].to]=i;
                if (!inq[e[i].to]){
                    q.push(e[i].to);
                    inq[e[i].to]=1;
                }
            }
        inq[h]=0;
    }
    return dis[t]!=-inf;
}
inline void mcf(){
    int x=inf;
    for(int i=from[t];i;i=from[e[i].from]) 
        x=min(x,e[i].c);
    ans1+=x;

    for(int i=from[t];i;i=from[e[i].from]){
        ans2+=x*e[i].w,e[i].c-=x,e[i^1].c+=x;
    }
}

int main(){
    l=read(),r=read();
    For(i,l,r){
        addedge(s,i,1,0);
        addedge(i+1000,t,1,0);
    }
    For(i,l,r) For(j,l,r)
        if (judge(i,j)&&i!=j) addedge(i,j+1000,1,i+j);
    while (spfa()) mcf();
    printf("%d %d\n",ans1/2,ans2/2);
    return 0;
}