题意：M个影片，其属性有开始时间S，结束时间T，类型op和权值val。有K个人，每个人可以看若干个时间不相交的影片，其获得的收益是这个影片的权值val，但如果观看的影片相邻为相同的属性，那么收益要减少W。每个影片只能被一个人看。求所有人能获得的收益值之和的最大值。
分析：因为人数不定，所以贪心和dp的思路被否定了。1对多的带权匹配，求最大权，这种问题显然KM是解决不了的，那么只能是最小费用最大流了。而这题要求的是最大收益，那么建负权边即可。
为了保证每个影片只被一个人观看，将其拆为入点和出点，入点和出点之间连一条容量为1，花费为0的边，网络流建图的基本操作。
首先虚拟一个源点st和源点big。从big向st建一条容量为K，花费为0的边，表示有K个人可以进行接下来选影片的操作。
从st点向每个入点连一条容量为1，花费为-val[i]的边，表示每个影片都可以作为某个人最先观看的影片。
若两个影片的时间不相交（u->T <= v->S），那么在u到v之间建一条容量为1，花费为-val[v]的边；若u,v属性相同则花费为-val[v]+W。
最后将每个出点向汇点连一条容量为1，花费为0的边。
跑出的最小花费取反就是所求答案。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = ;
const int MAXM = ;
const int INF = 0x3f3f3f3f;
struct Edge{
int to, next, cap, flow, cost;
} edge[MAXM];
int head[MAXN], tol;
int pre[MAXN], dis[MAXN];
bool vis[MAXN];
int N; //0~N-1的点数
void init(int n)
{
N = n;
tol = ;
memset(head, -, sizeof(head));
} void addedge(int u, int v, int cap, int cost)
{
edge[tol].to = v;
edge[tol].cap = cap;
edge[tol].cost = cost;
edge[tol].flow = ;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = ;
edge[tol].cost = -cost;
edge[tol].flow = ;
edge[tol].next = head[v];
head[v] = tol++;
} bool spfa(int s, int t){
queue<int> q;
for (int i = ; i < N; i++){
dis[i] = INF;
vis[i] = false;
pre[i] = -;
}
dis[s] = ;
vis[s] = true;
q.push(s);
while (!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for (int i = head[u]; i != -; i = edge[i].next){
int v = edge[i].to; if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost){
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if (!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
if (pre[t] == -) return false;
else return true;
} int minCostMaxflow(int s, int t, int &cost){
int flow = ;
cost = ;
while (spfa(s, t)){
int Min = INF;
for (int i = pre[t]; i != -; i = pre[edge[i ^ ].to]){
if (Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
}
for (int i = pre[t]; i != -; i = pre[edge[i ^ ].to]){
edge[i].flow += Min;
edge[i ^ ].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
} int n,M,K,W; struct Node{
int s,t,op,val;
}pt[MAXN]; int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int T; scanf("%d",&T);
while(T--){
scanf("%d %d %d %d",&n, &M, &K, &W);
int st = ,big =*M+;
int ed = big+;
init(*M+);
addedge(big,st,K,);
for(int i=;i<=M;++i){
scanf("%d%d%d%d",&pt[i].s,&pt[i].t, &pt[i].val, &pt[i].op);
addedge(st,i,,-pt[i].val);
addedge(i+M,ed,,);
addedge(i,i+M,,);
}
for(int i=;i<=M;++i){
for(int j=;j<=M;++j){
if(i==j) continue;
if(pt[i].t<=pt[j].s){
if(pt[i].op^pt[j].op){
addedge(i+M,j,,-pt[j].val);
}
else{
addedge(i+M,j,,-(pt[j].val-W));
}
}
}
}
int res;
minCostMaxflow(big,ed,res);
printf("%d\n",-res);
}
return ;
}