以下是我今天解题的题解报告:
[1] intervals(Poj1201)
题目描述
一个整数集合Z有n个区间,每个区间有3个值,ai,bi,ci代表,在区间[ai,bi]上至少有ci个整数属于集合Z,ci可以在区间内任意取不重复的点。
现在要满足所有区间的约束条件,问最少可选多少个点。
输入
第一行一个整数n,表示区间个数
以下n行描述区间,第i+1行,三个整数ai,bi,ci,由空格隔开,其中 0 <= ai <= bi <= 50000 且1 <= ci <= bi - ai+1.

输出
一行,输出满足要求序列的长度的最小值
样例输入
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
样例输出
6
思路:
要理解差分约束和最短路的关系,差分约束就是一系列不等式的条件约束,把不等式移成相同形式之后可以构造边,把差分约束问题转换成求最短路(或者最长路)的问题。如果输入3 6 2的话就是表示[3, 6]这个区间至少需要选择2个点,可以是3,4也可以是4,6(总情况有 C(4, 2)种 )。需要将问题进行一下转化,考虑到最后需要求的是一个完整区间内至少有多少点被选中,试着用d[i]表示[0, i]这个区间至少有多少点能被选中,可以知道 d[-1] = 0,对于每个区间描述,可以表示成d[ bi ] - d[ ai - 1 ] >= ci,而我们的目标要求的是 d[ 50000 ] - d[ -1 ] >= T 这个不等式中的T,将所有区间描述转化成图后求-1到50000的最长路。 -1不能映射,所以可以将所有点都向x轴正方向偏移1个单位(即所有数+1)
这里忽略了一些要素,因为d[i]描述了一个求和函数,所以对于d[i]和d[i-1]其实是有自身限制的,考虑到每个点有选和不选两种状态,所以d[i]和d[i-1]需要满足以下不等式: 0 <= d[i] - d[i-1] <= 1 (即第i个数选还是不选)。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio> 
#include<queue>
#define ll long long
using namespace std;
#define INF 0x3f3f3f3f

struct Edge
{
    int u,v,w,next;
    Edge(){}
    Edge(int u_,int v_,int w_)
    {
        u = u_;
        v = v_;
        w = w_;
    }
}edges[200000];

int head[50010];
int d[50010];
int e = 0,maxnum = 0;
void addedge(int u,int v,int w)
{
    edges[e] = Edge(u,v,w);
    edges[e].next = head[u];
    head[u] = e++;
}

int inq[50010];
void spfa()
{
    queue<int> q;
    while(!q.empty()) q.pop();
    for(int i=0;i<=maxnum;i++) d[i] = -INF;
    d[0] = 0;
    memset(inq,0,sizeof(inq));
    q.push(0);
    inq[0] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        inq[u]--;
        for(int i=head[u];i!=-1;i=edges[i].next)
        {
            int v = edges[i].v;
            if(d[v] < d[u] + edges[i].w)
            {
                d[v] = d[u] + edges[i].w;
                if(!inq[v])
                {
                    inq[v]++;
                    q.push(v);
                }
            }
        }
    }
}

int main()
{
	int n,u,v,w;
	scanf("%d",&n);
	memset(head,-1,sizeof(head));
	maxnum=0,e=0;
	for(int i = 0 ; i < n; i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		maxnum = max(maxnum,v+1);
		addedge(u,v+1,w);
	}
	for(int i = 0 ; i <= maxnum ; i++)
	{
		addedge(i,i+1,0);
		addedge(i+1,i,-1);
	}
	spfa();
	printf("%d\n",d[maxnum]);
	return 0;
}


[2] [SCOI2011]糖果(Bzoj2330)
题目描述
幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。
输入
输入的第一行是两个整数N,K。
接下来K行,表示这些点需要满足的关系,每行3个数字,X,A,B。
如果X=1, 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多;
如果X=2, 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果;
如果X=3, 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果;
如果X=4, 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果;
如果X=5, 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果;
输出
输出一行,表示lxhgww老师至少需要准备的糖果数,如果不能满足小朋友们的所有要求,就输出-1。
样例输入
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
样例输出
11
思路:
SPFA(注意这个是用spfa求出单元最大路)+差分约束;分析一下x取不同值建边的情况,当x=1时,我们可以把AB两个小朋友的边的权值赋成0,就是add(x,y,0)和add(y,x,0)。当x=2时,两种情况,A小朋友和B小朋友是同一个人,这里要特判,就输出-1,否则的话,我们就建有一条A到B权值为1的边,就是add(x,y,1);当x=3时,因为说尽可能少耗费糖果,所以我们可以把不少于当做等于来处理,就是赋值为0,就是add(y,x,0);剩下x=4~5时同理省略。

 #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100005
using namespace std;
int n,K,hd,tl,dst[MAXN],que[MAXN],Tim[MAXN];
long long Ans;
bool vis[MAXN];
int tot,lnk[MAXN],nxt[4*MAXN],son[4*MAXN],w[4*MAXN];
void Add(int x,int y,int z)
{
	son[++tot]=y;
	w[tot]=z;
	nxt[tot]=lnk[x];
	lnk[x]=tot;
}
bool SPFA(int x)
{
    hd=0;
	que[tl=1]=x;
	Tim[x]=1;
	vis[x]=1;
    while(hd^tl)
	{
        x=que[(++hd)%=MAXN];
		vis[x]=0;
        for(int j=lnk[x];j;j=nxt[j])
        if(dst[x]+w[j]>dst[son[j]])
		{
            dst[son[j]]=dst[x]+w[j];
            if(++Tim[son[j]]>=n) return 0;
            if(!vis[son[j]])
			{
				
			vis[son[j]]=1;
			que[(++tl)%=MAXN]=son[j];
			} 
        }
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&K);
    for(int i=1;i<=K;i++)
	{
        int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
        if(opt==1) Add(x,y,0),Add(y,x,0);
		else if(opt==2)
		{
			if(x==y)
			{
				printf("-1\n");
				return 0;
			}
			Add(x,y,1);
		}
		else if(opt==3) Add(y,x,0);
		else if(opt==4)
		{
			if(x==y)
			{
				printf("-1\n");
				return 0;
			}
			Add(y,x,1);
		}else Add(x,y,0);
    }
    for(int i=n;i;i--) Add(0,i,1);
    if(!SPFA(0)) printf("-1\n");
	else
	{
        for(int i=1;i<=n;i++) Ans+=dst[i];
        printf("%lld\n",Ans);
    }
    return 0;
}