大致题意
给定 n，m，k，W,分别表示一天有n小时，有m个电视节目，有k个人观看，每个电视节目有 2 种类型 0 or 1，如果一个人连续看了2种相同 的类型的节目 就会扣除 W的快乐值，每个电视节目只能供 1 个人观看。接下来 m 行，每行 4 个量：li，ri，vi，typi。分别表示电视节目的起点，终点，快乐值，类型。一个人看的节目不能有时间冲突。求 k 个人看节目能获得的最大快乐值。
思路
容易想到拆点费用流，每个节目拆成两个点，i 向 i’ 连容量为1费用为 vi 的边，限制每个节目只能共一个人观看，节目之间连边，i’ 向所有 lj > ri 的 j 连一条容量为1，费用为 （typj==typi ? -W:0)的边。然后设一个超前的原点汇点控制初始流量为 k 即人数。 最近两场都遇到这种模型，看来费用流用的还挺多。 我又试着写了spfa优化的费用流，又T了，改用djistra优化的板子，跑的飞快，看来出题人在造数据的时候会让你构造出网格图。所以spfa可能真的死了。
代码
#include<bits/stdc++.h>
using namespace std
;
#define maxn 605
#define maxm 1006
#define ll long long int
#define INF 0x3f3f3f3f
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define mem(a) memset(a,0,sizeof(a))
#define sqr(x) (x*x)
#define inf (ll)2e18+1
#define PI acos(-1)
#define mod 10007
#define auto(i,x) for(int i=head[x];i;i=ed[i].nxt)
#define ls x<<1
#define rs x<<1|1
ll
read(){
ll x
=0,f
=1ll;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-')f
=-1;ch
=getchar();}
while(isdigit(ch
))x
=x
*10+ch
-'0',ch
=getchar();
return f
*x
;
}
int n
,m
,T
,k
,W
;
struct node
{int l
,r
,val
,typ
;}a
[maxn
];
int s
,t
,se
,te
;
typedef pair
<int, int> pii
;
struct edge
{
int to
, cap
, cost
, rev
;
edge() {}
edge(int to
, int _cap
, int _cost
, int _rev
):to(to
), cap(_cap
), cost(_cost
), rev(_rev
) {}
};
int V
;
int h
[maxn
];
int dis
[maxn
];
int prevv
[maxn
];
int pree
[maxn
];
vector
<edge
> G
[maxn
];
void init(int n
) {
V
= n
;
for(int i
= 0; i
<= V
; ++i
) G
[i
].clear();
}
void addEdge(int from
, int to
, int cap
, int cost
){
G
[from
].push_back(edge(to
, cap
, cost
, G
[to
].size()));
G
[to
].push_back(edge(from
, 0, -cost
, G
[from
].size() - 1));
}
int MCMF(int s
, int t
, int f
, int &flow
){
int res
= 0;
for(int i
= 0; i
< 1 + V
; i
++) h
[i
] = 0;
while(f
){
priority_queue
<pii
, vector
<pii
>, greater
<pii
> > q
;
for(int i
= 0; i
< 1 + V
; i
++) dis
[i
] = INF
;
dis
[s
] = 0; q
.push(pii(0, s
));
while(!q
.empty()) {
pii now
= q
.top(); q
.pop();
int v
= now
.second
;
if(dis
[v
] < now
.first
) continue;
for(int i
= 0; i
< G
[v
].size(); ++i
) {
edge
&e
= G
[v
][i
];
if(e
.cap
> 0 && dis
[e
.to
] > dis
[v
] + e
.cost
+ h
[v
] - h
[e
.to
]){
dis
[e
.to
] = dis
[v
] + e
.cost
+ h
[v
] - h
[e
.to
];
prevv
[e
.to
] = v
;
pree
[e
.to
] = i
;
q
.push(pii(dis
[e
.to
], e
.to
));
}
}
}
if(dis
[t
] == INF
) break;
for(int i
= 0; i
<= V
; ++i
) h
[i
] += dis
[i
];
int d
= f
;
for(int v
= t
; v
!= s
; v
= prevv
[v
]) d
= min(d
, G
[prevv
[v
]][pree
[v
]].cap
);
f
-= d
; flow
+= d
; res
+= d
* h
[t
];
for(int v
= t
; v
!= s
; v
= prevv
[v
]) {
edge
&e
= G
[prevv
[v
]][pree
[v
]];
e
.cap
-= d
;
G
[v
][e
.rev
].cap
+= d
;
}
}
return res
;
}
int main()
{
T
=read();
while(T
--){
n
=read();m
=read();k
=read();W
=read();
s
=k
+2*m
+1;t
=s
+1;se
=s
+2;te
=s
+3;
init(te
);
inc(i
,1,m
){a
[i
].l
=read();a
[i
].r
=read();a
[i
].val
=read();a
[i
].typ
=read();}
inc(i
,1,m
)addEdge(i
,i
+m
,1,-a
[i
].val
);
inc(i
,1,k
)inc(j
,1,m
)addEdge(2*m
+i
,j
,1,0);
inc(i
,1,m
)inc(j
,1,m
)if(i
!=j
&&a
[j
].l
>=a
[i
].r
){
if(a
[i
].typ
==a
[j
].typ
)addEdge(i
+m
,j
,1,W
);
else addEdge(i
+m
,j
,1,0);
}
inc(i
,1,k
)addEdge(s
,2*m
+i
,1,0);
inc(i
,1,m
)addEdge(i
+m
,t
,1,0);
addEdge(se
,s
,k
,0);addEdge(t
,te
,k
,0);
int ans
;
printf("%d\n",-MCMF(se
,te
,INF
,ans
));
}
return 0;
}
