题目链接：https://cn.vjudge.net/contest/276233#problem/D
AC代码：
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = +;
const int maxedge= +;
int num,head[maxn];
int dis[maxn],vis[maxn];
int minx=inf;
int maxy=;
struct node
{
int fr;
int to;
int cost;
int nex;
} edge[maxedge];
struct point
{
int st;
int ed;
} po[maxn];
void init()
{
for(int i=; i<=; i++)
{
head[i]=-;
vis[i]=;
dis[i]=inf;
}
num=;
}
void addedge(int fr,int to,int cost)
{
edge[num].to=to;
edge[num].cost=cost;
edge[num].nex=head[fr];
head[fr]=num++;
}
ll spfa(int st,int ed)
{
dis[st]=;
vis[st]=;
queue<int>q;
q.push(st);
while(!q.empty())
{
int tmp=q.front();
q.pop();
vis[tmp]=;
for(int i=head[tmp]; i!=-; i=edge[i].nex)
{
int u=edge[i].to;
if(dis[u]>dis[tmp]+edge[i].cost)
{
dis[u]=dis[tmp]+edge[i].cost;
if(vis[u])
continue;
vis[u]=;
q.push(u);
}
}
}
return dis[ed];
}
int main()
{
int n,d;
scanf("%d",&n);
init();
for(int i=; i<=n; i++)
{
scanf("%d %d %d",&po[i].st,&po[i].ed,&d);
addedge(po[i].st-+,po[i].ed+,-d);//两个左边都+1，是为了防止出现变成-1的情况。
minx=min(minx,po[i].st);
maxy=max(maxy,po[i].ed+);
}
for(int i=minx; i<=maxy-; i++)
{
addedge(i,i+,);
addedge(i+,i,);
}
int ans=spfa(minx,maxy);
printf("%d\n",-ans);
return ;
}
E：
n个数的一个序列，m个约数，si, ni, oi, ki, 代表了序列中第si个数到第si+ni个数的和大于或小于ki，gt = 大于，lt = 小于
问是否存在相悖的约束
一个由memset引发的惨案，，，本来是用for循环初始化来着，结果这个题用for一直wa（后来发现是越界了--），然后改成memset的化就给过了。但是顺便加深了对建图的理解（理解写在上面了）。
AC代码：
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = +;
const int maxedge= +;
int num,head[maxn],out[maxn];
int dis[maxn],vis[maxn];
int n,m;
struct node
{
int fr;
int to;
int cost;
int nex;
} edge[maxedge];
struct point
{
int st;
int ed;
} po[maxn];
void init()
{
for(int i=; i<maxn; i++)
{
vis[i]=;
dis[i]=inf;
head[i]=-;
out[i]=;
}
num=;
num=;
}
void addedge(int fr,int to,int cost)
{
edge[num].to=to;
edge[num].cost=cost;
edge[num].nex=head[fr];
head[fr]=num++;
}
ll spfa(int st)
{
dis[st]=;
vis[st]=;
queue<int>q;
q.push(st);
while(!q.empty())
{
int tmp=q.front();
q.pop();
if(++out[tmp]>n+)
return -;
vis[tmp]=;
for(int i=head[tmp]; i!=-; i=edge[i].nex)
{
int u=edge[i].to;
if(dis[u]>dis[tmp]+edge[i].cost)
{
dis[u]=dis[tmp]+edge[i].cost;
if(vis[u])
continue;
vis[u]=;
q.push(u);
}
}
}
return ;
}
int main()
{
while(cin>>n)
{
init();
if(n==)
break;
cin>>m;
int u,v,d;
string str;
for(int i=; i<=m; i++)
{
cin>>u>>v>>str>>d;
if(str=="gt")
{
addedge(u,u+v+,-(d+));
}
else
{
addedge(v+u+,u,d-);
}
}
for(int i=; i<=n+; i++)
{
addedge(,i,);//超级源点的建立过程
}
int ans=spfa();
if(ans==-)
cout<<"successful conspiracy"<<endl;
else
cout<<"lamentable kingdom"<<endl;
}
return ;
}
G题：
给出数轴上的n个闭合int型区间。现在要在数轴上任意取一堆元素，构成一个元素集合V，要求给出的每个区间和元素集合V的交集至少有两个不同的元素，求集合V最小的元素个数。
超级源点的建立，为了保证整个区间的连通的，我们就需要建立一个超级源点来使得整个图是连通的，但是注意一点，在正常建边的时候，如果是大的指向小的，这个时候我们建立超级源点的时候就也应该遵循这个原则，如果是是小的指向大的，我们建立超级源点的时候反过来就可以了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = +;
const int maxnedge=+;
struct node
{
int nex;
int to;
int cost;
} edge[maxnedge];
int head[maxn],vis[maxn],dis[maxn],num;
void init()
{
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
memset(dis,inf,sizeof(dis));
num=;
}
void addedge(int fr,int to,int cost)
{
edge[num].to=to;
edge[num].nex=head[fr];
edge[num].cost=cost;
head[fr]=num++;
}
int spfa(int st,int ed)
{
queue<int>q;
dis[st]=;
vis[st]=;
q.push(st);
while(!q.empty())
{
int tmp=q.front();
q.pop();
vis[tmp]=;
for(int i=head[tmp]; i!=-; i=edge[i].nex)
{
int u=edge[i].to;
if(dis[u]>dis[tmp]+edge[i].cost)
{
dis[u]=dis[tmp]+edge[i].cost;
if(vis[u])
continue;
vis[u]=;
q.push(u);
}
}
}
return dis[ed];
}
int main()
{
init();
int n;
scanf("%d",&n);
int u,v;
int minx=inf,maxy=;
for(int i=; i<=n; i++)
{
scanf("%d %d",&u,&v);
u+=;
v+=;
addedge(u-,v,-);
addedge(v,u-,v-u+);
minx=min(minx,u-);
maxy=max(maxy,v);
}
int st=maxy+;
for(int i=minx; i<maxy; i++){
addedge(st,i,);
addedge(i,i+,);
addedge(i+,i,);
}
addedge(st,maxy,);
int ans=spfa(st,maxy);
printf("%d\n",-ans);
return ;
}