hdu 6437 Videos 拆点+最小费用最大流

你的名字 2022-01-21 02:39 288阅读 0赞

## 题意：给出n，每天有n个小时。有m种电影，每个电影有开始时间和结束时间，和01两种种类，k个人，每一部电影只能被一个人看，会获得一个快乐值wi，如果一个人连续看两部相同种类的电影，快乐值会消耗W，（先加上wi，再减去W）。如果两部电影的开始时间和结束时间是重合的，则可以连续看。题目保证所有的wi都大于等于W。 ##

## 分析：拆点，将每一部电影拆成 i 和 i+m   两个点，建立一条费用为 -wi，流量为1的边，如果两部电影可以连着看，则建边，同种类的费用为W，不同种类的费用为0，建立一个源点连向所有电影，一个汇点也连接所有电影，一个超级源点，流量为k，连着源点。然后跑最小费用最大流，答案取负就可以了。为什么这样就可以呢，因为题目保证了所有wi都大于W，也就是说，一部电影带来的收益肯定是正的，如果这个收益取负，那么我们就要最小的收益，而尽可能多的人就可以看尽可能多的电影，所以流量就要尽量大，这样就满足费用流的性质。 ##

![1096315-20180822182747511-299859425.png][]

## 参考博客：[https://blog.csdn.net/ccsu\_cat/article/details/81975288][https_blog.csdn.net_ccsu_cat_article_details_81975288] ##

## [https://www.cnblogs.com/xcantaloupe/p/9519617.html][https_www.cnblogs.com_xcantaloupe_p_9519617.html] ##

## [https://www.cnblogs.com/mountaink/p/9813897.html][https_www.cnblogs.com_mountaink_p_9813897.html] ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=405;
    const int inf=1e8;
    struct Edge
    {
    	int from,to,cap,flow,cost;
    };
    struct MCMF
    {
    	int n,m,s,t;
    	vector<Edge>edges;
    	vector<int>G[maxn];
    	int inq[maxn];
    	int d[maxn];
    	int p[maxn];
    	int a[maxn];
    	void init(int n)
    	{
    		this->n=n;
    		for(int i=0;i<n;i++)G[i].clear();
    		edges.clear();
    	}
    	void AddEdge(int from,int to,int cap,int cost)
    	{
    		edges.push_back((Edge){from,to,cap,0,cost});
    		edges.push_back((Edge){to,from,0,0,-cost});
    		m=edges.size();
    		G[from].push_back(m-2);
    		G[to].push_back(m-1);
    	}
    	bool Bellmanford(int s,int t,int& flow,int& cost)
    	{
    		for(int i=0;i<n;i++)d[i]=inf;
    		memset(inq,0,sizeof(inq));
    		d[s]=0;inq[s]=1;p[s]=0;a[s]=inf;
    		queue<int>Q;
    		Q.push(s);
    		while(!Q.empty())
    		{
    			int u=Q.front();Q.pop();
    			inq[u]=0;
    			for(int i=0;i<G[u].size();i++)
    			{
    				Edge& e=edges[G[u][i]];
    				if(e.cap>e.flow&&d[e.to]>d[u]+e.cost)
    				{
    					d[e.to]=d[u]+e.cost;
    					p[e.to]=G[u][i];
    					a[e.to]=min(a[u],e.cap-e.flow);
    					if(!inq[e.to])
    					{
    						Q.push(e.to);
    						inq[e.to]=1;
    					}
    				}
    			}
    		}
    		if(d[t]==inf)return false;
    		flow+=a[t];
    		cost+=d[t]*a[t];
    		int u=t;
    		while(u!=s)
    		{
    			edges[p[u]].flow+=a[t];
    			edges[p[u]^1].flow-=a[t];
    			u=edges[p[u]].from;
    		}
    		return true;
    	}
    	int Maxcost(int s,int t)
    	{
    		int flow=0,cost=0;
    		while(Bellmanford(s,t,flow,cost));
    		return -cost;
    	}
    }solve;///Bellmanford 模板
    struct node
    {
    	int l,r,cost,kind;
    }a[maxn];
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		solve.init(maxn);
    		int n,m,k,w;
    		scanf("%d%d%d%d",&n,&m,&k,&w);
    		int s=2*m,s1=s+1,t=s+2;
    		for(int i=0;i<m;i++) scanf("%d%d%d%d",&a[i].l,&a[i].r,&a[i].cost,&a[i].kind);
    		for(int i=0;i<m;i++)
    		{
    			solve.AddEdge(s1,i,1,0);
    			solve.AddEdge(i,i+m,1,-a[i].cost);
    			solve.AddEdge(i+m,t,1,0);
    			for(int j=0;j<m;j++)
    			if(a[i].r<=a[j].l&&i!=j)
    			{
    				int cost=0;
    				if(a[i].kind==a[j].kind)
    				cost=w;
    				solve.AddEdge(i+m,j,1,cost);
    			}
    		}
    		solve.AddEdge(s,s1,k,0);///k个人对应的k个流
    		printf("%d\n",solve.Maxcost(s,t));
    	}
    	return 0;
    }

[1096315-20180822182747511-299859425.png]: /images/20220121/98d344456ead4166b1d3a05ea6cc9f7e.png
[https_blog.csdn.net_ccsu_cat_article_details_81975288]: https://blog.csdn.net/ccsu_cat/article/details/81975288
[https_www.cnblogs.com_xcantaloupe_p_9519617.html]: https://www.cnblogs.com/xcantaloupe/p/9519617.html
[https_www.cnblogs.com_mountaink_p_9813897.html]: https://www.cnblogs.com/mountaink/p/9813897.html