NFLS-DAY 11

Posted on By 张, 高畅 NFLS-DAY 11无评论

T0

由于前天写完blog的时候blog显示链接失效，
于是……dddd，我的blog全没了(QAQ)
那我们现在开始吧。

T1

LUOGU
普通的模板。

#include
using namespace std;
const int N=1005,M=20005,INF=1e8;
int n,m,S,T,h[N],e[M],ne[M],f[M],idx;
int st[N],d[N],q[N],pre[N];
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
int bfs()
{
    int hh=0,tt=0;
    memset(st,0,sizeof st);
    q[0]=S;
    st[S]=1;
    d[S]=INF;
    while(hh<=tt)
    {
        int u=q[hh++];
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(!st[j]&&f[i])
            {
                st[j]=1;
                d[j]=min(d[u],f[i]);
                pre[j]=i;
                if(j==T)return 1;
                q[++tt]=j;
            }
        }
    }
    return 0;
}
int EK()
{
    int r=0;
    while(bfs())
    {
        r+=d[T];
        for(int i=T;i!=S;i=e[pre[i]^1])
        {
            f[pre[i]]-=d[T];
            f[pre[i]^1]+=d[T];
        }
    }
    return r;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);
    S=1;
    T=n; 
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    printf("%d\n",EK());
    return 0;
}

T2

LUOGU
将桌子与人当做二分图进行连边。

#include
using namespace std;
const int N=430,M=(150*270+N)*2,INF=1e8;
int n,m,S,T,h[N],e[M],ne[M],f[M],idx,q[N],d[N],cur[N];
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
int bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    q[0]=S;
    d[S]=0;
    cur[S]=h[S];
    while(hh<=tt)
    {
        int u=q[hh++];
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1&&f[i])
            {
                d[j]=d[u]+1;
                cur[j]=h[j];
                if(j==T)return 1;
                q[++tt]=j;
            }
        }
    }
    return 0;
}
int find(int u,int limit)
{
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int j=e[i];
        if(d[j]==d[u]+1&&f[i])
        {
            int t=find(j,min(f[i],limit-flow));
            if(!t)d[j]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int r=0,flow;
    while(bfs())
    {
        while(flow=find(S,INF))r+=flow;
    }
    return r;
}
int main()
{
    scanf("%d%d",&m,&n);
    S=0;
    T=m+n+1;
    memset(h,-1,sizeof h);
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        int c;
        scanf("%d",&c);
        sum+=c;
        add(S,i,c);
    }
    for(int i=1;i<=n;i++)
    {
        int c;
        scanf("%d",&c);
        add(m+i,T,c);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)add(i,m+j,1);
    }
    if(dinic()!=sum)puts("0");
    else
    {
        puts("1");
        for(int i=1;im&&e[j]<=m+n&&!f[j])printf("%d ",e[j]-m);
            }
            puts("");
        }
    }
    return 0;
}

T3

LUOGU
先用Floyd求出最短路，然后做最大流。

#include
using namespace std;
const int N=405,M=(N*N+2*N)+5;
typedef long long LL;
const LL INF=1e15;
int n,m,S,T;
int cow[N],house[N];
int h[N],e[M],ne[M],idx;
LL f[M];
int q[N],d[N],cur[N];
LL sum,dist[N][N];
void add(int a,int b,LL c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
int bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    q[0]=S;
    d[S]=0;
    cur[S]=h[S];
    while(hh<=tt)
    {
        int u=q[hh++];
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1&&f[i])
            {
                d[j]=d[u]+1;
                cur[j]=h[j];
                if(j==T)return 1;
                q[++tt]=j;
            }
        }
    }
    return 0;
}
LL find(int u,LL limit)
{
    if(u==T)return limit;
    LL flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int j=e[i];
        if(d[j]==d[u]+1&&f[i])
        {
            LL t=find(j,min(f[i],limit-flow));
            if(!t)d[j]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}
LL dinic()
{
    LL r=0,flow;
    while(bfs())
    {
        while(flow=find(S,INF))r+=flow;
    }
    return r;
}
int check(LL mid)
{
    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=n;i++)
    {
        add(S,i,(LL)cow[i]);
        add(i+n,T,(LL)house[i]);
        for(int j=1;j<=n;j++)
        {
            if(i==j||dist[i][j]=sum;
}
int main()
{
    scanf("%d%d",&n,&m);
    S=(n<<1)+1;
    T=(n<<1)+2;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&cow[i],&house[i]);
        sum+=(LL)cow[i];
        for(int j=1;j<=n;j++)dist[i][j]=INF;
        dist[i][i]=0;
    }
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        dist[a][b]=min(dist[a][b],(LL)c);
        dist[b][a]=min(dist[b][a],(LL)c);
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
    LL l=1,r=INF;
    while(l>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%lld",(l==INF?-1:l));
    return 0;
}

T4

LUOGU
还是最大流，但是需要拆点，将牛拆成两个点，一个连食物，一个连饮料。

#include
using namespace std;
const int N=405,M=40605,INF=1e8;
int n,S,T;
int h[N],e[M],f[M],ne[M],idx,d[N],q[N],cur[N];
void add(int a,int b,int c){e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++,e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;}
int bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    q[0]=S,d[S]=0,cur[S]=h[S];
    while(hh<=tt)
    {
        int u=q[hh++];
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1&&f[i])
            {
                d[j]=d[u]+1;
                cur[j]=h[j];
                if(j==T)return 1;
                q[++tt]=j;
            }
        }
    }
    return 0;
}
int find(int u,int limit)
{
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int j=e[i];
        if(d[j]==d[u]+1&&f[i])
        {
            int t=find(j,min(f[i],limit-flow));
            if(!t)d[j]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int r=0,flow;
    while(bfs())
    {
        while(flow=find(S,INF))r+=flow;
    }
    return r;
}
int main()
{
    int D,F;
    memset(h,-1,sizeof h);
    scanf("%d%d%d",&n,&F,&D);
    T=(n<<1)+F+D+1;
    for(int i=1;i<=F;i++)add(S,(n<<1)+i,1);
    for(int i=1;i<=D;i++)add((n<<1)+F+i,T,1);
    for(int i=1;i<=n;i++)
    {
        add(i,n+i,1);
        int a,b,c;
        scanf("%d%d",&a,&b);
        while(a--)
        {
            scanf("%d",&c);
            add((n<<1)+c,i,1);
        }
        while(b--)
        {
            scanf("%d",&c);
            add(n+i,(n<<1)+F+c,1);
        }
    }
    printf("%d",dinic());
    return 0;
}

T5

给你n个点，然后给你一些点之间的路，然后让你求从1到n有多少条路径不重复的最短路

本题是HDOJ原题，不过前几年HDOJ因网站安全问题不再对外开放。
用dijkstra/spfa算出1~n的最短路。
然后再次求最大流。

#include 
using namespace std;
const int N = 1505, M = 500005, INF = 1e8;
int n, S, T;
int h[N], e[M], f[M], ne[M], idx;
vector<pair > G[N];
struct node1 {
    int q[N], d[N], cur[N];
    void add(int a, int b, int c) {
        e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++, e[idx] = a, f[idx] = 0, ne[idx] = h[b],
        h[b] = idx++;
    }
    int bfs() {
        int hh = 0, tt = 0;
        memset(d, -1, sizeof d);
        q[0] = S, d[S] = 0, cur[S] = h[S];
        while (hh <= tt) {
            int u = q[hh++];
            for (int i = h[u]; ~i; i = ne[i]) {
                int j = e[i];
                if (d[j] == -1 && f[i]) {
                    d[j] = d[u] + 1;
                    cur[j] = h[j];
                    if (j == T)
                        return 1;
                    q[++tt] = j;
                }
            }
        }
        return 0;
    }
    int find(int u, int limit) {
        if (u == T)
            return limit;
        int flow = 0;
        for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
            cur[u] = i;
            int j = e[i];
            if (d[j] == d[u] + 1 && f[i]) {
                int t = find(j, min(f[i], limit - flow));
                if (!t)
                    d[j] = -1;
                f[i] -= t;
                f[i ^ 1] += t;
                flow += t;
            }
        }
        return flow;
    }
    int dinic() {
        int r = 0, flow;
        while (bfs()) {
            while (flow = find(S, INF)) r += flow;
        }
        return r;
    }
} MF;
struct node2 {
    int st[N], dist[N];
    void spfa() {
        memset(st, 0, sizeof st);
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        queue q;
        q.push(1);
        st[1] = 1;
        while (q.size()) {
            auto t = q.front();
            q.pop();
            st[t] = 0;
            for (int i = 0; i  dist[t] + w) {
                    dist[j] = dist[t] + w;
                    if (!st[j]) {
                        q.push(j);
                        st[j] = 1;
                    }
                }
            }
        }
    }
} SP;
struct node3 {
    int a, b, c;
};
vector E;
void work() {
    int a, b, c;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) G[i].clear();
    E.clear();
    memset(h, -1, sizeof h);
    idx = 0;
    while (1) {
        scanf("%d%d%d", &a, &b, &c);
        if (!a && !b && !c)
            break;
        E.push_back({ a, b, c });
        G[a].push_back({ b, c });
        G[b].push_back({ a, c });
    }
    SP.spfa();
    if (n == 1 || SP.dist[n] == 0x3f3f3f3f) {
        puts("0");
        return;
    }
    S = 0, T = n + 1;
    MF.add(0, 1, INF);
    for (int i = 0; i < E.size(); i++) {
        a = E[i].a, b = E[i].b, c = E[i].c;
        if (SP.dist[a] - SP.dist[b] == c)
            MF.add(b, a, 1);
        else if (SP.dist[b] - SP.dist[a] == c)
            MF.add(a, b, 1);
    }
    MF.add(n, T, INF);
    printf("%d\n", MF.dinic());
}
int main() {
    int cases;
    scanf("%d", &cases);
    while (cases--) work();
}

T6

LUOGU
二分答案后最大流。

#include
using namespace std;
const int N=4e4+5;
const int M=N<<2,INF=1e8;
int n,m,S,T;
int h[N],e[M],ne[M],f[M],idx;
int d[N],q[N],cur[N],pos[N];
pairG[N]; 
void add(int a,int b,int c){e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++,e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;}
int bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    q[0]=S;
    d[S]=0;
    cur[S]=h[S];
    while(hh<=tt)
    {
        int u=q[hh++];
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1&&f[i])
            {
                d[j]=d[u]+1;
                cur[j]=h[j];
                if(j==T)return 1;
                q[++tt]=j;
            }
        }
    }
    return 0;
}
int find(int u,int limit)
{
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int j=e[i];
        if(d[j]==d[u]+1&&f[i])
        {
            int t=find(j,min(f[i],limit-flow));
            if(!t)d[j]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int r=0,flow;
    while(bfs())
    {
        while(flow=find(S,INF))r+=flow;
    }
    return r;
}
int check(int mid)
{
    memset(h,-1,sizeof h);
    idx=0;
    S=0;
    T=n+m+1;
    for(int i=1;i<=m;i++)
    {
        add(S,i,1);
        add(i,G[i].first+m,1);
        pos[i]=idx-2;
        add(i,G[i].second+m,1);
    }
    for(int i=1;i=m;
}
int main()
{   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&G[i].first,&G[i].second);
    int l=0,r=m;
    while(l>1;
        if(check(mid))r=mid;
        else l=mid+1;   
    } 
    printf("%d\n",l);
    check(l);
    for(int i=1;i<=m;i++)printf("%d\n",(!f[pos[i]]));
    return 0;
}

T7

ACWING
难在建图上，建源点S向顾客连容量为需求的边，猪圈向汇点T连容量为+∞的边，然后顾客与猪圈以某种方式连边，最后的最大流即为答案。

#include 
using namespace std;
const int N = 105, M = 200405, INF = 1e8;
int n, m, S, T, w[M], l[M];
int h[N], e[M], ne[M], f[M], idx;
int d[N], q[N], cur[N];
void add(int a, int b, int c) {
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++, e[idx] = a, f[idx] = 0, ne[idx] = h[b],
    h[b] = idx++;
}
int bfs() {
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S;
    d[S] = 0;
    cur[S] = h[S];
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && f[i]) {
                d[j] = d[u] + 1;
                cur[j] = h[j];
                if (j == T)
                    return 1;
                q[++tt] = j;
            }
        }
    }
    return 0;
}
int find(int u, int limit) {
    if (u == T)
        return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i;
        int j = e[i];
        if (d[j] == d[u] + 1 && f[i]) {
            int t = find(j, min(f[i], limit - flow));
            if (!t)
                d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}
int dinic() {
    int r = 0, flow;
    while (bfs()) {
        while (flow = find(S, INF)) r += flow;
    }
    return r;
}
int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &m, &n);
    T = n + 1;
    for (int i = 1; i <= m; i++) scanf("%d", &w[i]);
    for (int i = 1; i <= n; i++) {
        int k, x;
        scanf("%d", &k);
        while (k--) {
            scanf("%d", &x);
            if (!l[x])
                add(S, i, w[x]);
            else
                add(l[x], i, INF);
            l[x] = i;
        }
        scanf("%d", &x);
        add(i, T, x);
    }
    printf("%d", dinic());
    return 0;
}

T8

LUOGU
二维=>(hash)一维，然后建图去做。

#include
using namespace std;
const int N=10005,M=200005,INF=1e8;
int n,m,S,T;
int h[N],e[M],f[M],ne[M],idx;
int d[N],q[N],now[N];
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
int bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    q[0]=S;
    d[S]=0;
    now[S]=h[S];
    while(hh<=tt)
    {
        int u=q[hh++];
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1&&f[i])
            {
                d[j]=d[u]+1;
                now[j]=h[j];
                if(j==T)return 1;
                q[++tt]=j;
            }
        }
    }
    return 0;
}
int find(int u,int limit)
{
    if(u==T)return limit;
    int ans=0;
    for(int i=now[u];~i&&ans<limit;i=ne[i])
    {
        now[u]=i;
        int j=e[i];
        if(d[j]==d[u]+1&&f[i])
        {
            int v=find(j,min(f[i],limit-ans));
            if(!v)d[j]=-1;
            f[i]-=v;
            f[i^1]+=v;
            ans+=v;
        }
    }
    return ans;
}
int dinic()
{
    int res=0;
    while(bfs())
    {
        int ans=0;
        while(ans=find(S,INF))res+=ans;
    }
    return res;
}
int get(int x,int y){return x*m+y;}
int main()
{
    int sum=0;
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    S=0,T=get(n,m)+1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            sum+=x;
            if((i+j)&1)
            {
                add(S,get(i,j),x);
                if(i1)add(get(i,j),get(i-1,j),INF);
                if(j1)add(get(i,j),get(i,j-1),INF);
            }
            else add(get(i,j),T,x);
        }
    }
    printf("%d",sum-dinic());
    return 0;
}

T9

LUOGU
建图跑最小割，由定理，最大流=最小割，因此代码基本没怎么变

#include
using namespace std;
const int N=305,M=2e5+5,INF=1e8;
int n,m,S,T;
int h[N],e[M],ne[M],f[M],idx;
int q[N],d[N],cur[N];
void add(int a,int b,int c){e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++,e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;}
int bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    q[0]=S,d[S]=0,cur[S]=h[S];
    while(hh<=tt)
    {
        int u=q[hh++];
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1&&f[i])
            {
                d[j]=d[u]+1;
                cur[j]=h[j];
                if(j==T)return 1;
                q[++tt]=j;
            }
        }
    }
    return 0;
}
int find(int u,int limit)
{
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int j=e[i];
        if(d[j]==d[u]+1&&f[i])
        {
            int t=find(j,min(f[i],limit-flow));
            if(!t)d[j]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int r=0,flow;
    while(bfs())
    {
        while(flow=find(S,INF))r+=flow;
    }
    return r;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    S=0;
    T=n+1;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if(x)add(S,i,1);
        else add(i,T,1);
    }
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b,1);
        add(b,a,1);
    }
    printf("%d\n",dinic());
    return 0;
}

T10

ACWING
求费用流（类似模板）

#include 
using namespace std;
const int N = 155, M = 10305, INF = 1e8;
int n, m, S, T;
int h[N], e[M], ne[M], f[M], w[M], idx;
int q[N], d[N], pre[N], incf[N], st[N];
void add(int a, int b, int c, int d) {
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++, e[idx] = a, f[idx] = 0, w[idx] = -d,
    ne[idx] = h[b], h[b] = idx++;
}
int spfa() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt) {
        int u = q[hh++];
        if (hh == N)
            hh = 0;
        st[u] = 0;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (f[i] && d[j] > d[u] + w[i]) {
                d[j] = d[u] + w[i];
                pre[j] = i;
                incf[j] = min(f[i], incf[u]);
                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N)
                        tt = 0;
                    st[j] = 1;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (spfa()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1]) {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
    return cost;
}
int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &m, &n);
    T = m + n + 1;
    for (int i = 1; i <= m; i++) {
        int a;
        scanf("%d", &a);
        add(S, i, a, 0);
    }
    for (int i = 1; i <= n; i++) {
        int b;
        scanf("%d", &b);
        add(m + i, T, b, 0);
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int c;
            scanf("%d", &c);
            add(i, m + j, INF, c);
        }
    }
    printf("%d\n", EK());
    for (int i = 0; i < idx; i += 2) f[i] += f[i ^ 1], f[i ^ 1] = 0, w[i] = -w[i], w[i ^ 1] = -w[i ^ 1];
    printf("%d", -EK());
    return 0;
}

T11

给定一个n*n的矩阵，矩阵方格中有数，每次可以从一个格子走到向下或向右的格子并取走格子上的数，现在求两条从左上角到右下角的不相交的路径，使取走的数的和最大。 

#include 
using namespace std;
const int N = 760005, INF = 1e8;
int n, m, S, T, a[605][605];
int h[N], e[N * 10], ne[N * 10], f[N * 10], w[N * 10], idx;
int q[N * 10], d[N], pre[N], incf[N], st[N];
void add(int a, int b, int c, int d) {
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++, e[idx] = a, f[idx] = 0, w[idx] = -d,
    ne[idx] = h[b], h[b] = idx++;
}
int spfa() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt) {
        int u = q[hh++];
        if (hh == N)
            hh = 0;
        st[u] = 0;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (f[i] && d[j] > d[u] + w[i]) {
                d[j] = d[u] + w[i];
                pre[j] = i;
                incf[j] = min(f[i], incf[u]);
                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N)
                        tt = 0;
                    st[j] = 1;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (spfa()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1]) {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
    return cost;
}
int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) scanf("%d", &a[i][j]);
        }
        memset(h, -1, sizeof h);
        idx = 0;
        S = 0;
        T = 2 * n * n - 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                add(i * n + j, i * n + j + n * n, 1, -a[i][j]);
                if ((!i && !j) || (i == n - 1 && j == n - 1))
                    add(i * n + j, i * n + j + n * n, 1, 0);
                if (i + 1 < n)
                    add(i * n + j + n * n, (i + 1) * n + j, 1, 0);
                if (j + 1 < n)
                    add(i * n + j + n * n, i * n + j + 1, 1, 0);
            }
        }
        printf("%d\n", -EK());
    }
    return 0;
}

T12

LUOGU
还是费用流。

#include
using namespace std;
const int N=100005,M=200005,INF=1e8;
int n,m,S,T;
int h[N],e[M],ne[M],f[M],w[M],idx;
int q[N],d[N],pre[N],incf[N],st[N];
void add(int a,int b,int c,int d){e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;}
void ADD(int a,int b,int c,int d){add(a,b,c,d),add(b,a,0,-d);}
int spfa()
{
    int hh=0,tt=1;
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S,d[S]=0,incf[S]=INF;
    while(hh!=tt)
    {
        int u=q[hh++];
        if(hh==N)hh=0;
        st[u]=0;
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(f[i]&&d[j]>d[u]+w[i])
            {
                d[j]=d[u]+w[i];
                pre[j]=i;
                incf[j]=min(f[i],incf[u]);
                if(!st[j])
                {
                    q[tt++]=j;
                    if(tt==N)tt=0;
                    st[j]=1;
                }
            }
        }
    }
    return incf[T]>0;
}
int EK()
{
    int cost=0;
    while(spfa())
    {
        int t=incf[T];
        cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1])
        {
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
    return cost;
}
int get(int i,int j){return (i-1)*n+j;}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    S=0;
    T=2*n*n+1;
    ADD(S,get(1,1),m,0);
    ADD(get(n,n)+n*n,T,m,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x;
            scanf("%d",&x);
            x=-x;
            ADD(get(i,j),get(i,j)+n*n,1,x);
            ADD(get(i,j),get(i,j)+n*n,INF,0);
            if(i<n)ADD(get(i,j)+n*n,get(i+1,j),INF,0);
            if(j<n)ADD(get(i,j)+n*n,get(i,j+1),INF,0);
        }   
    }
    printf("%d",-EK());
    return 0;
}

T13

LUOGU
将i天分成两个点，一个点 i1表示用完的旧毛巾，一个点 i2表示需要的新毛巾。

#include
using namespace std;
const int N=1605,M=10005,INF=1e8;
int n,p,S,T,x,xp,y,yp;
int h[N],e[M],ne[M],f[M],w[M],idx;
int q[N],d[N],pre[N],incf[N],st[N];
void add(int a,int b,int c,int d){e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++,e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;}
int spfa()
{
    int hh=0,tt=1;
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S,d[S]=0,incf[S]=INF;
    while(hh!=tt)
    {
        int u=q[hh++];
        if(hh==N)hh=0;
        st[u]=0;
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(f[i]&&d[j]>d[u]+w[i])
            {
                d[j]=d[u]+w[i];
                pre[j]=i;
                incf[j]=min(f[i],incf[u]);
                if(!st[j])
                {
                    q[tt++]=j;
                    if(tt==N)tt=0;
                    st[j]=1;
                }
            }
        }
    }
    return incf[T]>0;
}
int EK()
{
    int cost=0;
    while(spfa())
    {
        int t=incf[T];
        cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1])
        {
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
    return cost;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d%d%d%d%d",&n,&p,&x,&xp,&y,&yp);
    S=0,T=n*2+1;
    for(int i=1;i<=n;i++)
    {
        int r;
        scanf("%d",&r);
        add(S,i,r,0);
        add(n+i,T,r,0);
        add(S,n+i,INF,p);
        if(i<n)add(i,i+1,INF,0);
        if(i+x<=n)add(i,n+i+x,INF,xp);
        if(i+y<=n)add(i,n+i+y,INF,yp);
    }
    printf("%d",EK());
    return 0;
}
训练日志

发表回复