[SCOI2011]糖果 题解

洛谷题面

看到很多题解并没有讲清楚这道题为什么可以用某些方法，套个板子就没了。蒟蒻就发一篇题解装X造福大家吧233

做这道题前，我推荐大家做一下一本通中的1352：【例4-13】奖金一题，因为有可能做完了这道题对于你们会有一点启发。

题目分析

题目对于小朋友的嫉妒一共有\(5\)中情况，分别如下：

·如果 X=1， 表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的糖果一样多；

·如果 X=2， 表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果；

·如果 X=3， 表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果；

·如果 X=4， 表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果；

·如果 X=5， 表示第 A 个小朋友分到的糖果必须不多于第 B 个小朋友分到的糖果；

题目想要让每个小朋友都满足且使用最少的糖果数量，如果无解则输出-1。

我们将小朋友当做点，小朋友之间限制条件当做边

对于X=1、X=3、X=5时，我们不难知道，想要使用最少的糖果数量，那么最好的方式就是两个人糖果数量一样。

对于X=2，那么A=B-1最优

对于X=4，那么B=A-1最优

所以说了做一下一本通中的1352：【例4-13】奖金一题对于你们会有一点启发。

现在我们又可以想到，让每个小朋友都满足且使用最少的糖果数量，那么只需要通过别人对它没有限制的小朋友，依次更新每个小朋友要有的糖即可。

那么怎么去依次找小朋友并更新每个小朋友要的糖呢？

拓扑排序！

怎么建图？按什么条件去建？

比如A要少于B，则建一条A->B的边，这样拓扑排序下来，可以保证处理每个点的糖果数量时，可以从小处理到大，符合上面的要求。

那X=1、3、5和X=2、4时有什么区别呢？

我们就需要额外记录边权，X=1、3、5边权为0，X=2、4边权为1。

血的教训：X=1时需要建双向边！即A->B且B->A。

为什么？

因为A必须与B一样多，那么我们就可以使用Tarjan缩点将两个点合并为1个点，且将环变为强连通分量。正好满足了拓扑排序不能有环的性质。

怎么判断无解情况？

在建新图用来拓扑排序时，看两个点是否在同一个环内，在且边权为1则无解。

最重要的一个问题：怎么更新糖果数量？

我们将每个人的糖果当做dp[i]，在删i相连的点的入度时，更新i的next的dp值

则有动态转移方程：

dp[当前更新的点] = max(dp[当前更新的点],dp[当前删除的点] + nnei[当前删除的点][第j个邻居].边权)

这些知识本人Blog中都会涉及的233

那么思路就很明显了：

建图(X=1:建边权为0的双向边，X=2、X=4建边权为1的单向边，X=3、X=5时建边权为0的单向边)——>Tarjan——>边建新图边判断无解——>用新图拓扑排序，并更新每个点所需要的糖果数量

代码

#include
using namespace std;

const int MAXN = 100000 + 10;

int n,k;
int scc[MAXN],sum,low[MAXN],dfn[MAXN],cnt,tot[MAXN];
//以上是强连通图的必备变量，唯一tot是记录每个强连通分量里面有多少个点 
int dp[MAXN];
//这个用于DP记录答案 
int in[MAXN];
//这个记录入度，用于Topo 
long long ans;
//最终答案 
struct Node{
	int next;//记录每个点的下一个点 
	int v;//记录边权 
};
vectornei[MAXN];//旧图 
vectornnei[MAXN];//新图 
bool Stack[MAXN];//用于Tarjan 
stack s;//用于Tarjan

inline int read(){//快速读入 
    int f = 1, x = 0;
    char c = getchar();

    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }

    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }

    return f * x;
}


void Tarjan(int u){//Tarjan模板 
	low[u] = dfn[u] = ++cnt;
	Stack[u] = true;
	s.push(u);
	
	int len = nei[u].size();
	for(int i = 0;i < len; i++){
		int next = nei[u][i].next;
		
		if(dfn[next] == 0){
			Tarjan(next);
			low[u] = min(low[u],low[next]);
		}else
		if(Stack[next]){
			low[u] = min(low[u],dfn[next]);
		}
	}
	
	if(dfn[u] == low[u]){
		sum++;
		scc[u] = sum;
		Stack[u] = false;
		tot[sum]++;
		
		while(s.top() != u){
			Stack[s.top()] = false;
			scc[s.top()] = sum;
			s.pop();
			tot[sum]++;
		}
		s.pop();
	}
}

int main()
{
	n = read(),k = read();//读入 
	
	for(int i = 1;i <= k; i++){
		int z = read(),x = read(),y = read();
		switch(z){//使用开关函数 
			case 1:{//一号情况 
				nei[x].push_back((Node){y,0});
				nei[y].push_back((Node){x,0});
				//这里一定要建两条边！ 
				break;
			}
			case 2:{//二号情况 
				nei[x].push_back((Node){y,1});
				break;
			}
			case 3:{//三号情况 
				nei[y].push_back((Node){x,0});
				break;
			}
			case 4:{//四号情况 
				nei[y].push_back((Node){x,1});
				break;
			}
			case 5:{//五号情况 
				nei[x].push_back((Node){y,0});
				break;
			}
		}
	}

	for(int i = 1;i <= n; i++){
    	if(dfn[i] == 0)Tarjan(i);//Tajan 
    }

    for(int i = 1;i <= n; i++){//建新图 
    	int len = nei[i].size();
		
		for(int j = 0;j < len; j++){
			int next = nei[i][j].next;
			int xx = scc[i];
        	int yy = scc[next];
        
        	if(xx == yy && nei[i][j].v == 1){//判断无解  
        		cout<<-1<<"\n";
        		return 0;
			}
        
        	if(xx != yy){//建新图 
        	    nnei[xx].push_back((Node){yy,nei[i][j].v});
        	    in[yy]++;
        	}
		}
    }
    
    queueq;//Topo模板 
    
    for(int i = 1;i <= sum; i++){//将入读为0的压入队列 
    	if(!in[i]){
    		q.push(i);
    		dp[i] = 1;//初始化 
		}
	}
	
	while(!q.empty()){//拓扑模板 
		int cur = q.front();
		q.pop();
		int len = nnei[cur].size();
		
		for(int i = 0;i < len; i++){
			int next = nnei[cur][i].next;
			in[next]--;
			dp[next] = max(dp[next],dp[cur] + nnei[cur][i].v);//Dp方程 
			
			if(!in[next])q.push(next);
		}
	}
	
	for(int i = 1;i <= sum; i++){//累加答案 
		ans += (long long) dp[i] * tot[i];
	}
	cout<