2018 Multi-University Training Contest 10 Problem L.Videos(最小费用流)

题意：一个video拥有四个属性-----开始时间，结束时间，happiness，type，给定K个人，一部片子只能被一个人看，一个人连续看x次同类型的片子(x>=2)会失去x*W的happiness,问K个人一天内看video的最大happiness和.

首先我们将一个video看作一个点.

之后，由于限定了连续看同类型的片子会掉happiness，所以我们这里引入一个拆点，点i到他的拆点i+m的流量为1,cost为costi，

我们再将拆点与可连的所有点相连，如果两个点的type一样，cost为W，否则为0,

最后将源点与次源点相连，流量为K，次源点与i相连，流量为1,跑一遍板子就ok了.

板子源自隔壁队什么都会的yhz

#include<bits/stdc++.h>
using namespace std;
const int maxn=200*200+5;
const int N=200*200+5;
#define inf 0x3f3f3f3f
struct edge
{int to,Next,c;int cost;
} e[maxn];
int cnt,head[N];
int s,t;
int dis[N],pre[N],path[N];
bool vis[N];
void add(int u,int v,int c,int cost)
{e[cnt].to=v;e[cnt].c=c;e[cnt].cost=cost;e[cnt].Next=head[u];head[u]=cnt++;e[cnt].to=u;e[cnt].c=0;e[cnt].cost=-cost;e[cnt].Next=head[v];head[v]=cnt++;
}
bool spfa()
{memset(pre,-1,sizeof pre);memset(dis,inf,sizeof dis);memset(vis,0,sizeof vis);dis[s]=0;vis[s]=1;queue<int>q;q.push(s);while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=head[x]; ~i; i=e[i].Next){int te=e[i].to;if(e[i].c>0&&dis[x]+e[i].cost<dis[te]){dis[te]=dis[x]+e[i].cost;pre[te]=x;path[te]=i;if(!vis[te])q.push(te),vis[te]=1;}}}return pre[t]!=-1;
}
int mincostmaxflow()
{int cost=0,flow=0;while(spfa()){int f=inf;for(int i=t; i!=s; i=pre[i])if(e[path[i]].c<f)f=e[path[i]].c;flow+=f;cost+=dis[t]*f;for(int i=t; i!=s; i=pre[i]){e[path[i]].c-=f;e[path[i]^1].c+=f;}}return cost;
}
void init()
{memset(head,-1,sizeof head);cnt=0;
}
struct node
{int s,t,c,w,op;
} te[N];
int main()
{int T;scanf("%d",&T);while(T--){init();int n,m,K,W;scanf("%d%d%d%d",&n,&m,&K,&W);for(int i=2;i<=m+1;i++){int s,t,w,op;scanf("%d%d%d%d",&s,&t,&w,&op);te[i]={s,t,1,w,op};}for(int i=2;i<=m+1;i++){for(int j=2;j<=m+1;j++){if(i!=j){if(te[i].t <= te[j].s){if(te[i].op==te[j].op) add(i+m,j,1,W);else add(i+m,j,1,0);}}}}add(0,1,K,0);for(int i=2;i<=m+1;i++) add(1,i,1,0),add(i,i+m,1,-te[i].w),add(i+m,2*m+2,1,0);s=0,t=2*m+2;printf("%d\n",-mincostmaxflow());}
}