2 10 3 1 10 1 5 1000 0 5 10 1000 1 3 9 10 0 10 3 1 10 1 5 1000 0 5 10 1000 0 3 9 10 0
2000 1990
题目大意：一天有N个小时，有m个节目（每种节目都有类型），有k个人，连续看相同类型的节目会扣w快乐值
每一种节目有都一个播放区间[l,r]。每个人同一时间只能看一个节目，看完可以获得快乐值。问最多可以获得多少快乐？
我们拆点 用于限制两个相连节目的费用
然后次源点用于限制k个人
#include<bits/stdc++.h> #define FIN freopen("input.txt","r",stdin) #define ll long long #define mod 1000000007 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f const int maxn = 100005; using namespace std; int head[maxn],Next[maxn*200],to[maxn*200]; int flow[maxn*200],dis[maxn],pre[maxn],vis[maxn],id[maxn],ct[maxn]; int cnt,s,t,n,m,k; inline void add(int u,int v,int w,int cost){ Next[cnt]=head[u]; head[u]=cnt; to[cnt]=v; flow[cnt]=w; ct[cnt++]=cost; Next[cnt]=head[v]; head[v]=cnt; to[cnt]=u; flow[cnt]=0; ct[cnt++]=-cost; } bool spfa(){ memset(vis,0,sizeof(vis)); memset(dis,inf,sizeof(dis)); memset(pre,-1,sizeof(pre)); dis[s]=0; queue<int> q; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=Next[i]){ int v=to[i]; int d=ct[i]; if(dis[v]>dis[u]+d&&flow[i]>0){ dis[v]=dis[u]+d; pre[v]=u; id[v]=i; if(!vis[v]){ vis[v]=1; q.push(v); } } } } // cout<<dis[t]<<endl; return dis[t]<inf; } int Maxflow(){ int ans=0; while(spfa()){ int Min=inf; for(int i=t;i!=s;i=pre[i]){ Min=min(flow[id[i]],Min); } for(int i=t;i!=s;i=pre[i]){ flow[id[i]]-=Min; flow[id[i]^1]+=Min; } ans+=dis[t]*Min; } return ans; } void init(){ memset(head,-1,sizeof(head)); cnt=0; } struct node{ int l,r,op,val; }p[205]; int main(){ int T,w; scanf("%d",&T); while(T--){ init(); scanf("%d %d %d %d",&n,&m,&k,&w); s=0; int ss=m+m+1; t=m+m+2; for(int i=1;i<=m;i++){ scanf("%d %d %d %d",&p[i].l,&p[i].r,&p[i].val,&p[i].op); } for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++){ if(i==j) continue; if(p[j].l>=p[i].r){ add(i+m,j,1,p[i].op==p[j].op?w:0); // cout<<i+m<<" "<<j<<" "<<(p[i].op==p[j].op?-w:0)<<endl; } } } add(s,ss,k,0); /* cout<<s<<" "<<ss<<" 0\n";*/ for(int i=1;i<=m;i++){ add(ss,i,1,0); add(i+m,t,1,0); add(i,i+m,1,-p[i].val); /* cout<<ss<<" "<<i<<" 0\n"; cout<<i+m<<" "<<t<<" 0\n"; cout<<i<<" "<<i+m<<" "<<-p[i].val<<endl;*/ } printf("%d\n",-Maxflow()); } return 0; }
原文：https://www.cnblogs.com/MengX/p/11370478.html
