（ 图论专题 ）【 最大费用最大流 】

【 最大费用最大流 】只需要将【 最小费用最大流 】的w取相反数就好了，最后的mincost（ 最小费用 ）也取相反数就是最大费用了。

（ 图论专题 ）【 最小费用最大流 】

例题：HDU - 6437 

10 3 1 10
1 5 1000 0
5 10 1000 1

第一行n,m,K,M, 每天n个小时，m个视频，K个人，观看相同视频时失去W幸福值。

接下来m行，每行S，T，w，op四个正整数，dii个视频的开始时间，结束时间，看完得到的幸福值，类型。

题意：每天有n小时，m个视频，k个人，每个视频只允许一个人看一次，每个视频有开始时间和结束时间以及种类A和种类B，不能同时看两个视频（ [1,3], [3,5] 这样可以连续看 ）。每个人看视频将得到一个快乐值w，如果交替看不同种类的视频如ABABA那么不会减小快乐值，否则看一次与之前重复类型的视频就减少W的快乐值。如AABBAAA则减少4次快乐值。即4W。问最大化的快乐值是多少。

思路：最大费用最大流，人数是流，幸福值是费用。

建图方式如下，（我写的代码中：除了视频的拆分点之间f=1， 其他地方f=人数。）

小技巧：刚开始就按照最小费用最大流来写，全写完了再统一把addedge的W全改成相反数。不然容易写乱。

（ 图来源：https://www.cnblogs.com/xcantaloupe/p/9519617.html ）

代码：

#include <bits/stdc++.h>
#define inf 0x3f3f3f3fusing namespace std;const int maxn = 1e5+10;
struct node {int to,w,f,nxt;
} e[maxn];
int n,m,s,t,maxflow,mincost;
int dis[maxn],flow[maxn],via[maxn],pre[maxn],last[maxn];
int head[maxn],cnt=0;void addedge( int u, int v, int f, int w )
{e[cnt].to = v;e[cnt].f = f;e[cnt].w = w;e[cnt].nxt = head[u];head[u] = cnt++;
}int spfa()
{memset(dis,inf,sizeof(dis));memset(flow,inf,sizeof(flow));memset(via,0,sizeof(via));queue <int> Q;Q.push(s); via[s]=1; dis[s]=0; pre[t]=-1;while ( !Q.empty() ) {int x = Q.front(); Q.pop(); via[x]=0;for ( int i=head[x]; i!=-1; i=e[i].nxt ) {int y = e[i].to, f=e[i].f, w=e[i].w;if ( f && dis[y]>dis[x]+w ) { // 只要最短流能更新就更新dis[y] = dis[x] + w;pre[y] = x; // y 的父节点是xlast[y] = i; // y点连接其父节点的边，编号为iflow[y] = min(flow[x],f); // 源点到y点的最大流量。会被最小的一个分支限制住if ( via[y]==0 ) {    // 只有队列中没有当前值才往队列里加。Q.push(y); via[y]=1;}}}}return pre[t]!=-1; // 判断汇点是否有点连入，即还存不存在增广路。初始化pre[t]=-1.
}void MCMF()
{maxflow = mincost = 0;while ( spfa() ) { // 还存在增广路就进入int x = t;maxflow += flow[t]; // 源点到t点的最大流量mincost += flow[t]*dis[t];while ( x!=s ) {  // 递归改变边的流量e[last[x]].f -= flow[t];e[last[x]^1].f += flow[t];x = pre[x];}}
}struct nodee {int ss,tt,ww,op;
}vid[205];int main()
{int T;cin>>T;while ( T-- ) {memset(head,-1,sizeof(head));cnt=0;int n,m,K,W;cin>>n>>m>>K>>W;s = m*2+5; t=m*2+7;int ss = m*2+6;addedge(s,ss,K,0);addedge(ss,s,0,0);for ( int i=0; i<m; i++ ) {cin>>vid[i].ss>>vid[i].tt>>vid[i].ww>>vid[i].op;addedge( i, i+m, 1, -vid[i].ww );addedge( i+m, i, 0, vid[i].ww );addedge( ss, i, K, 0 );addedge( i, ss, 0, 0 );addedge( i+m, t, K, 0 );addedge( t, i+m, 0, 0 );}for ( int i=0; i<m; i++ ) {for ( int j=0; j<m; j++ ) {if ( vid[j].ss>=vid[i].tt ) {if ( vid[j].op==vid[i].op ) {addedge( i+m, j, K, W );addedge( j, i+m, 0, -W );}else {addedge( i+m, j, K, 0 );addedge( j, i+m, 0, 0 );}}}}MCMF();cout << -mincost << endl;}return 0;
}