查分约束：
差分约束系统其实就是一种限制的关系，转换为一张图，然后跑一边SPFA，更新一遍，
P1984奖学金
题目描述：
期末考试终于完了，老班决定召开班委会，内容嘛，则是可爱的奖学金的问题，她叫来了一些班委，每位班委提出了自己的意见：“我认为同学a的奖学金应该比b多！”老班决定要找出一种奖学金方案，满足各位班委的意见，且同时使得总奖学金数最少。每位同学奖学金最少为100元且都为整数。
输入：
- 第一行两个整数n,m，表示同学总数和班委意见数;
- 以下m行，每行2个整数a,b，表示某个班委认为第a号同学奖学金应该比第b号同学高
输出：
若无法找到合法方案，则输出“impossible”(不含引号）；否则输出一个数表示最少总奖学金。
题解：
我们将里面的a>b转换为a=b+1，就可以建造一张这样的关系图了b到a存在着边权为1的路，然后我们就跑一遍SPFA美滋滋，更新出来所有符合要求的奖学金，如果不符合要求就直接退出输出impossible，如果符合就累加起来输出。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct Edge
{
int Point;
int Next;
}a[20000];
int n,m,x,y,Link[20000],len;
int dis[20000],Queue[20000];
long long head,tail,ans,Money[20000];
inline int In()
{
int This=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9')
{ if(ch=='-') F=-F; ch=getchar();}
while(ch>='0'&&ch<='9')
{ This=(This<<1)+(This<<3)+ch-'0';ch=getchar();}
return This*F;
}
bool Topsort_SPFA()
{
for(int i=1;i<=n;i++)
if(!dis[i]) Queue[++tail]=i;
while(++head<=tail)
for(int i=Link[Queue[head]];i;i=a[i].Next)
{
int This=a[i].Point; dis[This]--;
Money[This]=max(Money[This],Money[Queue[head]]+1);
if(!dis[This]) Queue[++tail]=This;
if(dis[This]<0) return false;
}
sort(Money+1,Money+n+1);
if(Money[1]<0) return false;
else return true;
}
int main()
{
n=In(); m=In();
for(int i=1;i<=m;i++)
{
y=In(); x=In();
a[++len].Point=y;
a[len].Next=Link[x];
Link[x]=len;
dis[y]++;
}
for(int i=1;i<=n;i++) Money[i]=100;
if(!Topsort_SPFA()||tail!=n) cout<<"impossible"<<endl;
else {
for(int i=1;i<=n;i++) ans+=Money[i];
cout<<ans<<endl;
}
return 0;
}
|
P1985糖果
题目描述：
幼儿园里有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。
题解：
这道题好烦好烦，因为这道题不但麻烦的，而且第六组数据时需要进行逆向加边的，因为顺着地会超时，没错，十万个点的一条链，然后是就是理所应当的超时了，所以我们需要逆向加边……心累不说了，我要去搞树状数组了！QAQ
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| #include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
struct Edge
{
int Point;
int Next;
int Value;
}a[2000000];
int n,m,x,y,z,len,head,tail,Queue[200000];
int Link[200000],Candy[200000],dis[200000];
long long ans;
bool vis[200000];
inline int In()
{
int This=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9')
{ if(ch=='-') F=-F; ch=getchar();}
while(ch>='0'&&ch<='9')
{ This=(This<<1)+(This<<3)+ch-'0';ch=getchar();}
return This*F;
}
void Init(int x,int y,int v)
{
a[++len].Point=y;
a[len].Next=Link[x];
a[len].Value=v;
Link[x]=len;
}
bool SPFA()
{
Queue[++tail]=0;
vis[0]=true;
dis[0]=true;
while(++head<=tail)
{
cout<<Queue[head]<<endl;
for(int i=Link[Queue[head]];i;i=a[i].Next)
{
int This=a[i].Point;
if(Candy[This]<Candy[Queue[head]]+a[i].Value)
{
Candy[This]=Candy[Queue[head]]+a[i].Value;
if(++dis[This]>=n) return false;
if(vis[This]==false)
{
Queue[++tail]=This;
vis[This]=true;
}
}
}
vis[Queue[head]]=false;
}
}
int main()
{
n=In(); m=In();
for(int i=1;i<=m;i++)
{
z=In(); x=In(); y=In();
if(z==1)
{
Init(x,y,0);
Init(y,x,0);
}
if(z==2)
{
if(x==y)
{
cout<<-1<<endl;
return 0;
}
Init(x,y,1);
}
if(z==3) Init(y,x,0);
if(z==4)
{
if(x==y)
{
cout<<-1<<endl;
return 0;
}
Init(y,x,1);
}
if(z==5) Init(x,y,0);
}
for(int i=n;i;i--) Init(0,i,1);
if(!SPFA()) cout<<-1<<endl;
else {
for(int i=1;i<=n;i++)
ans+=Candy[i];
cout<<ans<<endl;
}
return 0;
}
|
