首先可以费用流建图,左边一堆点表示人,右边一堆点表示题,源点向每个人连floor(t/r)条边,费用依次为r,2r,3r….然后写了一个卡不过去,动态加边也卡不过去,然后我想：这里一定有一些不为人知的卡常黑科技!然后去查题解发现不是费用流…因为只有源点向人的连边有费用,那么费用流的过程其实是:考虑让尽量多的人做费用为r的第一道题,然后让尽量多的人做费用为2r的第二道题…然后我们发现,写一个动态加边的dinic就可以了…我这里没有加边,直接把源点向人连边的边权重置,效果是一样的.
边权重置之后就不能沿着反向边反悔了,但这道题的性质使得不考虑反悔的情况也是对的.如果考虑费用为r的时候让1号人做了1号题,然后考虑费用为2r的时候发现可以让2号人做1号题，1号人做2号题,这种情况是不会出现的，因为在考虑费用为r的时候就可以让2号人做1号题，1号人做2号题.
一开始跑费用流T了好几发,然后dinic当前弧优化写残了又T了好几发...
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1005,maxm=1000005; struct edge{ int to,next,w; }lst[maxm];int len=0,first[maxn],_first[maxn]; void addedge(int a,int b,int w){ lst[len].to=b;lst[len].next=first[a];lst[len].w=w;first[a]=len++; lst[len].to=a;lst[len].next=first[b];lst[len].w=0;first[b]=len++; } int q[maxn],dis[maxn],vis[maxn],s,t,head,tail,T; bool bfs(){ head=tail=0;vis[s]=++T;dis[s]=0;q[tail++]=s; while(head!=tail){ int x=q[head++]; for(int pt=first[x];pt!=-1;pt=lst[pt].next){ if(lst[pt].w&&vis[lst[pt].to]!=T){ dis[lst[pt].to]=dis[x]+1;vis[lst[pt].to]=T;q[tail++]=lst[pt].to; } } } if(vis[t]==T)memcpy(_first,first,sizeof(first)); return vis[t]==T; } int dfs(int x,int lim){ if(x==t)return lim; int flow=0,a; for(int pt=_first[x];pt!=-1;pt=lst[pt].next){ _first[x]=pt; if(lst[pt].w&&dis[lst[pt].to]==dis[x]+1&&(a=dfs(lst[pt].to,min(lst[pt].w,lim-flow)))){ lst[pt].w-=a;lst[pt^1].w+=a;flow+=a; if(lim==flow)return lim; } } return flow; } int dinic(){ int ans=0,x; while(bfs())while(x=dfs(s,0x7f7f7f7f))ans+=x; return ans; } int n,m,r,lim,k; int main(){ memset(first,-1,sizeof(first)); scanf("%d%d%d%d%d",&n,&m,&r,&lim,&k); s=0;t=n+m+1; for(int i=1;i<=m;++i)addedge(n+i,t,1); int a,b; for(int i=1;i<=k;++i){ scanf("%d%d",&a,&b); addedge(a,n+b,1); } int ans1=0,ans2=0; for(int i=1;i<=n;++i)addedge(s,i,1); for(int j=1;j*r<=lim;++j){ int tmp=dinic();ans1+=tmp;ans2+=tmp*j*r; if(tmp==0)break; for(int i=1;i<=n;++i){ lst[len-i*2].w=1;lst[len-i*2+1].w=0; } } printf("%d %d ",ans1,ans2); return 0; }