题面：https://www.luogu.com.cn/problem/P3529
题意：\(n\)个人\(m\)个题目，每个题要\(r\)分钟完成。比赛有\(t\)分钟。
给出每个人会做哪些题目，请你安排一个每个人在什么时候做什么题目，
使得做出来的题目数最多。在做题数一样多的情况下，罚时尽量小。
罚时为\(\sum\) 每道题做出来的时间
(1\(\le\)n,m \(\le\) 500,1 \(\le\) r,t \(\le\) 1e6)
题解：n,m都不大，考虑使用网络流。
可以看出，此题是二分图匹配模型，那就按套路来做：
\(S\) \(\Rightarrow\) 每个人，\(v=r/t\);
每个人 \(\Rightarrow\) 每道题，\(v=1\);
每道题 \(\Rightarrow\) \(T\)，\(v=1\)。
但这样的话，我们只能保证做题数最大，罚时不一定最少。
为什么呢？这就好像我和cjy大佬一起去打ACM,因为我太菜了，啥都不会做，
大佬不仅做了他能做的高难度题，可能还会抢了我的题，从而造成罚时更多。
那这个问题如何解决呢？既然我们希望更多人参与进来，我们可以每次从
源点\(S\)向每个人释放1个流量，这样就避免了抢题的情况。当最大流不再
增加时，程序结束。
时间复杂度：O(网络流复杂度)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
template<class U>I read(U &res){
res=0;register U g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const int INF=1e9+7;
struct E{
int to,nt,w;
}e[303000];
#define T e[k].to
struct Match{
int x,y,s;
}ma[2020];
int n,m,S,D,r,t,p,M,cur[202000],tot=-1,sum,dis[202000],vis[202000],X[202000],Y[202000],head[202000],las,ans1,ans2,now;
I add(int x,int y,int w){
//cout<<"!"<<x<<" "<<y<<" "<<w<<endl;
e[++tot].to=y;
e[tot].nt=head[x];
head[x]=tot;
e[tot].w=1;
e[++tot].to=x;
e[tot].nt=head[y];
head[y]=tot;
e[tot].w=0;
}
IN D_1(int x,int lim){
// cout<<"!"<<x<<" "<<lim<<endl;
if(x==D||!lim)return lim;
re flow=0,ext;
for(re k=head[x];k!=-1;k=e[k].nt){
if(dis[x]+1==dis[T]&&e[k].w>0){
ext=D_1(T,min(lim,e[k].w));
if(!ext)continue;
flow+=ext;lim-=ext;
e[k].w-=ext;e[k^1].w+=ext;
if(!lim)break;
}
}
if(lim)dis[x]=-1;
//cout<<x<<" "<<flow<<endl;
return flow;
}
queue<int>q;
IN B_1(){
C(dis,-1);
dis[S]=0;
q.push(S);
memcpy(cur,head,sizeof(head));
while(!q.empty()){
p=q.front();q.pop();
for(re k=head[p];k!=-1;k=e[k].nt){
if(dis[T]==-1&&e[k].w>0){
//cout<<"@"<<p<<" "<<T<<" "<<k<<" "<<e[k].w<<endl;
dis[T]=dis[p]+1;
q.push(T);
}
}
}
return dis[D]!=-1;
}
I dinic(int _t){
re dt;
while(B_1()){dt=D_1(S,INF);ans1+=dt;ans2+=dt*_t;}
}
I get_match(int _t){
for(re k=0;k<=((M-1)<<1);k+=2){
if((!vis[T-n])&&(!e[k].w)){
sum++;
ma[sum].x=e[k^1].to;
ma[sum].y=T-n;
ma[sum].s=_t;
vis[T-n]=1;
}
}
}
int main(){
read(n);read(m);read(r);read(t);read(M);
C(head,-1);tot=-1;S=0;D=n+m+1;C(vis,0);
F(i,1,M){read(X[i]);read(Y[i]);add(X[i],n+Y[i],1);}
F(i,1,m)add(n+i,D,1);
now=r;las=ans1=ans2=sum=0;
while(now<=t){
//STS;
F(i,1,n)add(S,i,1);
dinic(now);
if(ans1==las)break;
las=ans1;
get_match(now-r);
now+=r;
}
printf("%d %d\n",ans1,ans2);
F(i,1,sum)printf("%d %d %d\n",ma[i].x,ma[i].y,ma[i].s);
return 0;
}