cjb-poi2011programmingcontest1

从 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 510
#define M 250010
#define LF double
#define stack stck
int g[N],nxt[M],v[M],f[N],b[N],tot=0;
int n,m,r,t,k;
void add(int x,int y)
{
    v[++tot]=y;
    nxt[tot]=g[x];
    g[x]=tot;
}
bool find(int x){
    for(int i=g[x];i;i=nxt[i])if(!b[v[i]]){
        b[v[i]]=1;
        if(!f[v[i]]||find(f[v[i]]))return f[v[i]]=x,1;
    }
    return 0;
}
int bad[N];
vector<int> work[N];
int main()
{
    cin>>n>>m>>r>>t>>k;
    rep(i,k)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }

    for(int j=1;j<=m;j++)f[j]=0;
    int ans=0;
    int anst=0;
    for(int ti=1;ti<=t/r;ti++)
    {
        for(int i=1;i<=n;i++)
        if (!bad[i])
        {
            for(int j=1;j<=m;j++)b[j]=0;
            if(find(i))ans++,anst+=ti;
            else bad[i]=1;
        }
        if (ans==m)break;
    }
    printf("%d %lld\n",ans,1ll*anst*r);
    rep(i,m)work[f[i]].pb(i);
    rep(i,n)
    {
        int wait=0;
        for(auto p:work[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 510
#define M 250010
#define LF double
#define stack stck
int g[N],nxt[M],v[M],f[N],b[N],tot=0;
int n,m,r,t,k;
void add(int x,int y)
{
    v[++tot]=y;
    nxt[tot]=g[x];
    g[x]=tot;
}
bool find(int x){
    for(int i=g[x];i;i=nxt[i])if(!b[v[i]]){
        b[v[i]]=1;
        if(!f[v[i]]||find(f[v[i]]))return f[v[i]]=x,1;
    }
    return 0;
}
int bad[N];
vector<int> work[N];
int main()
{
    cin>>n>>m>>r>>t>>k;
    rep(i,k)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    for(int j=1;j<=m;j++)f[j]=0;
    int ans=0;
    int anst=0;
    for(int ti=1;ti<=t/r;ti++)
    {
        for(int i=1;i<=n;i++)
        if (!bad[i])
        {
            for(int j=1;j<=m;j++)b[j]=0;
            if(find(i))ans++,anst+=ti;
            else bad[i]=1;
        }
        if (ans==m)break;
    }
    printf("%d %lld\n",ans,1ll*anst*r);
    rep(i,m)work[f[i]].pb(i);
    rep(i,n)
    {
        int wait=0;
        for(auto p:work[i]){ printf("%d %d %d\n",i,p,wait); wait+=r; }
    }
}