cjb-poi2011programmingcontest2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 1010
#define M 1000010
#define LF double
#define inf 2147483647
#define stack stck
struct EDGE { int adj, w, next; } edge[M];
int n,m,r,t,k, top, gh[N], nrl[N], S, T;
void addedge(int x, int y, int w) {
    edge[++top].adj = y;
    edge[top].w = w;
    edge[top].next = gh[x];
    gh[x] = top;
    edge[++top].adj = x;
    edge[top].w = 0;
    edge[top].next = gh[y];
    gh[y] = top;
}
int dist[N], q[N];
int bfs() {
    memset(dist, 0, sizeof(dist));
    q[1] = S; int head = 0, tail = 1; dist[S] = 1;
    while (head != tail) {
        int x = q[++head];
        for (int p=gh[x]; p; p=edge[p].next)
            if (edge[p].w && !dist[edge[p].adj]) {
                dist[edge[p].adj] = dist[x] + 1;
                q[++tail] = edge[p].adj;
            }
    }
    return dist[T];
}
int dinic(int x, int delta) {
    if (x==T) return delta;
    for (int& p=nrl[x]; p && delta; p=edge[p].next)
        if (edge[p].w && dist[x]+1 == dist[edge[p].adj]) {
            int dd = dinic(edge[p].adj, min(delta, edge[p].w));
            if (!dd) continue;
            edge[p].w -= dd;
            edge[p^1].w += dd;
            return dd;
        }
    return 0;
}
int work() {
    int ans = 0;
    while (bfs()) {
        memcpy(nrl, gh, sizeof(gh));
        int t; while (t = dinic(S, inf)) ans += t;
    }
    return ans;
}
pair<int,int> save[M];
vector<int> fuck[N];
int main()
{
    cin>>n>>m>>r>>t>>k; top=1;
    S=0; T=n+m+1;
    rep(i,n)addedge(S,i,1);
    rep(i,m)addedge(n+i,T,1);
    rep(i,k)
    {
        scanf("%d%d",&save[i].first,&save[i].second);
        addedge(save[i].first,n+save[i].second,1);
    }
    int ans=0;
    long long anst=0;
    rep(i,t/r)
    {
        rep(i,n)edge[2*i].w=1,edge[2*i+1].w=0;
        int flow=work(); ans+=flow; anst+=1ll*flow*i*r;
        if (!flow)break; 
    }
    cout<<ans<<" "<<anst<<endl;
    rep(i,k)if (edge[2*n+2*m+2*i].w==0)fuck[save[i].first].pb(save[i].second);
    rep(i,n)
    {
        int wait=0;
        for(auto p:fuck[i]){ printf("%d %d %d\n",i,p,wait); wait+=r; }
    }
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 1010
#define M 1000010
#define LF double
#define inf 2147483647
#define stack stck
struct EDGE { int adj, w, next; } edge[M];
int n,m,r,t,k, top, gh[N], nrl[N], S, T;
void addedge(int x, int y, int w) {
    edge[++top].adj = y;
    edge[top].w = w;
    edge[top].next = gh[x];
    gh[x] = top;
    edge[++top].adj = x;
    edge[top].w = 0;
    edge[top].next = gh[y];
    gh[y] = top;
}
int dist[N], q[N];
int bfs() {
    memset(dist, 0, sizeof(dist));
    q[1] = S; int head = 0, tail = 1; dist[S] = 1;
    while (head != tail) {
        int x = q[++head];
        for (int p=gh[x]; p; p=edge[p].next)
            if (edge[p].w && !dist[edge[p].adj]) {
                dist[edge[p].adj] = dist[x] + 1;
                q[++tail] = edge[p].adj;
            }
    }
    return dist[T];
}
int dinic(int x, int delta) {
    if (x==T) return delta;
    for (int& p=nrl[x]; p && delta; p=edge[p].next)
        if (edge[p].w && dist[x]+1 == dist[edge[p].adj]) {
            int dd = dinic(edge[p].adj, min(delta, edge[p].w));
            if (!dd) continue;
            edge[p].w -= dd;
            edge[p^1].w += dd;
            return dd;
        }
    return 0;
}
int work() {
    int ans = 0;
    while (bfs()) {
        memcpy(nrl, gh, sizeof(gh));
        int t; while (t = dinic(S, inf)) ans += t;
    }
    return ans;
}
pair<int,int> save[M];
vector<int> fuck[N];
int main()
{
    cin>>n>>m>>r>>t>>k; top=1;
    S=0; T=n+m+1;
    rep(i,n)addedge(S,i,1);
    rep(i,m)addedge(n+i,T,1);
    rep(i,k)
    {
        scanf("%d%d",&save[i].first,&save[i].second);
        addedge(save[i].first,n+save[i].second,1);
    }
    int ans=0;
    long long anst=0;
    rep(i,t/r)
    {
        rep(i,n)edge[2*i].w=1,edge[2*i+1].w=0;
        int flow=work(); ans+=flow; anst+=1ll*flow*i*r;
        if (!flow)break; 
    }
    cout<<ans<<" "<<anst<<endl;
    rep(i,k)if (edge[2*n+2*m+2*i].w==0)fuck[save[i].first].pb(save[i].second);
    rep(i,n)
    {
        int wait=0;
        for(auto p:fuck[i]){ printf("%d %d %d\n",i,p,wait); wait+=r; }
    }
}