4.17题目总结（图论题目）
Ezio_0420
2018-04-17 16:43:23
## [POJ 1511 Invitation Cards](http://poj.org/problem?id=1511)
给定一张带正权的有向图，有n个人要从点1出发走到1..n的所有点，然
后再走回点1，求他们走过的所有路径长度和的最小值。
n, m ≤ 1000000,时限8s
解法：
经典最短路变形，分别建出正向边和反向边以1为源点跑最短路。
如果用Dijkstra的话，复杂度是O((n + m) log n)
假如常数太大，这样做有可能会超时。换用SPFA就能以很快的速度通过了。复杂度是O(玄学)。
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e6+3;
const long long inf=0x7ffffffff;
int s=1,cnt1,cnt2,head1[N],head2[N],n,m,t;
ll d1[N],d2[N],ans;
struct tu{
int to,ne;
ll w;
}e1[N],e2[N];
inline void add1(int u,int v,ll w){
cnt1++;
e1[cnt1].to=v;
e1[cnt1].w=w;
e1[cnt1].ne=head1[u];
head1[u]=cnt1;
}
inline void add2(int u,int v,ll w){
cnt2++;
e2[cnt2].to=v;
e2[cnt2].w=w;
e2[cnt2].ne=head2[u];
head2[u]=cnt2;
}
queue<int>q;
bool inq[N];
void spfa1(){
fill(d1+1,d1+n+1,inf);
d1[s]=0;
q.push(s);
inq[s]=true;
while(!q.empty()){
int i = q.front();
q.pop();
inq[i]=false;
for(int j = head1[i];j;j=e1[j].ne){
int v=e1[j].to;
if(d1[v]>d1[i]+e1[j].w){
d1[v]=d1[i]+e1[j].w;
if(!inq[v]){
q.push(v);
inq[v]=true;
}
}
}
}
}
void spfa2(){
fill(d2+1,d2+n+1,inf);
d2[s]=0;
q.push(s);
inq[s]=true;
while(!q.empty()){
int i = q.front();
q.pop();
inq[i]=false;
for(int j = head2[i];j;j=e2[j].ne){
int v=e2[j].to;
if(d2[v]>d2[i]+e2[j].w){
d2[v]=d2[i]+e2[j].w;
if(!inq[v]){
q.push(v);
inq[v]=true;
}
}
}
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i = 1;i<=m;i++){
int u,v;
ll w;
scanf("%d%d%lld",&u,&v,&w);
add1(u,v,w);
add2(v,u,w);
}
spfa1();
spfa2();
ans=0;
// for(int i = 1;i<=n;i++){
// printf("%lld ",d1[i]);
// }
// puts(" ");
// for(int i = 1;i<=n;i++){
// printf("%lld ",d2[i]);
// }
// puts(" ");
for(int i = 1;i<=n;i++){
ans+=d1[i]+d2[i];
}
printf("%lld\n",ans);
memset(e1,0,sizeof(e1));
memset(e2,0,sizeof(e2));
memset(head1,0,sizeof(head1));
memset(head2,0,sizeof(head2));
memset(d1,0,sizeof(d1));
memset(d2,0,sizeof(d2));
cnt1=cnt2=0;
}
return 0;
}
```
------------
## [POJ1062 昂贵的聘礼](http://poj.org/problem?id=1062)
有n件物品，你想要获得其中的物品1。每个物品都有个直接购买的价
格，你也有一定的金币，但不幸的是你的钱可能不够。还好，可以用
别的物品来换购；具体来说，每件物品i都有若干种(可能为0)换购方
式，表示如果你有某件其他物品j，那么用j加上额外的一些钱，就可以
买到i了。
此外，每件物品都有一个等级。你购买的任意两件物品的等级差都不
能超过一个给定的值m。求在这些条件下，要想买到物品1，最少需要
多少金币。
n ≤ 100，价格及等级均为不超过1e9的正整数
解法：
枚举所购买的物品中的最低等级，相应算出最高等级，然后只用这些
物品建图跑最短路。复杂度O(n^3)。
------------
##[小K的农场](https://www.luogu.org/problemnew/show/P1993)
小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：
农场a比农场b至少多种植了c个单位的作物，
农场a比农场b至多多种植了c个单位的作物，
农场a与农场b种植的作物数一样多。
但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
输入输出格式
输入格式：
第一行包括两个整数 n 和 m，分别表示农场数目和小 K 记忆中的信息数目。
接下来 m 行：
如果每行的第一个数是 1，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至少多种植了 c 个单位的作物。
如果每行的第一个数是 2，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至多多种植了 c 个单位的作物。
如果每行的第一个数是 3，家下来有 2 个整数 a,b，表示农场 a 种植的数量和 b 一样多。
输出格式：
如果存在某种情况与小 K 的记忆吻合，输出“Yes”，否则输出“No”。
解法：
差分约束，没有负环即可
对于形如a-b<=c这样的式子，我们可以建立一条从b到a边权为c的有向边，然后先拓扑排序找出所有环，再对于每个环DFS一遍判断是不是负环即可。
~~这题我做的时候迷之多跑一遍bfs的spfa，后来观察数据发现用spfa的输出的都是Yes，于是又思考了一下，发现果然根本不用跑spfa~~
~~然后我又发现。。。根本不用拓扑排序~~
直接DFS！
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<climits>
using namespace std;
const int N = 1e5+3;
const int inf=INT_MAX;
int n,m,head[N],cnt;
int d[N];
struct tu{
int to,ne,w;
}e[4*N+1];
void add(int u,int v,int w){
cnt++;
e[cnt].w=w;
e[cnt].to=v;
e[cnt].ne=head[u];
head[u]=cnt;
}
//queue<int>q;
//bool inq[2*N+1];
//bool spfa(int s){
// fill(d+1,d+n+1,inf);
// d[s]=0;
// q.push(s);
// inq[s]=true;
// while(!q.empty()){
// int i = q.front();
// q.pop();
// inq[i]=false;
// for(int j = head[i];j;j=e[j].ne){
// int v = e[j].to;
// if(d[v]>d[i]+e[j].w){
// d[v]=d[i]+e[j].w;
// if(!inq[v]){
// q.push(v);
// inq[v]=true;
// }
// }
// }
// }
// return true;
//}
int in[N+1];
bool vis[N+1];
queue<int>p;
void topsort(){
for(int i = 1;i<=n+1;i++){
if(!in[i]) p.push(i);
}
while(!p.empty()){
int i = p.front();
vis[i]=1;
p.pop();
for(int j = head[i];j;j=e[j].ne){
int v = e[j].to;
in[v]--;
if(!in[v]) p.push(v);
}
}
}
bool ever[N+1];
bool dfs(int i){
ever[i]=true;
for(int j=head[i];j;j=e[j].ne){
int v=e[j].to,dis=d[i]+e[j].w;
if(vis[v]) continue;
if(dis<d[v]){
if(ever[v]) return true;
d[v]=dis;
if(dfs(v)) return true;
}
}
ever[i]=false;
return false;
}
int main(){
scanf("%d%d",&n,&m);
int x,a,b,c;
for(int i = 1;i<=m;i++){
scanf("%d",&x);
if(x==1){
scanf("%d%d%d",&a,&b,&c);
//a-b>=c
add(a,b,-c);
in[b]++;
}
if(x==2){
scanf("%d%d%d",&a,&b,&c);
//a-b<=c;
add(b,a,c);
in[a]++;
}
if(x==3){
scanf("%d%d",&a,&b);
add(a,b,0);
in[b]++;
add(b,a,0);
in[a]++;
}
}
for(int i = 1;i<=n;i++){
add(n+1,i,0);
in[i]++;
}
topsort();
for(int i = 1;i<=n+1;i++){
if(!vis[i]){
if(dfs(i)){
puts("No");
return 0;
}
}
}
//bool ans=spfa(n+1);
//if(ans)
puts("Yes");
//else printf("No\n");
return 0;
}
```
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<climits>
using namespace std;
const int N = 1e5+3;
const int inf=INT_MAX;
int n,m,head[N],cnt;
int d[N];
struct tu{
int to,ne,w;
}e[2*N+1];
void add(int u,int v,int w){
cnt++;
e[cnt].w=w;
e[cnt].to=v;
e[cnt].ne=head[u];
head[u]=cnt;
}
bool ever[N+1];
bool dfs(int i){
ever[i]=true;
for(int j=head[i];j;j=e[j].ne){
int v=e[j].to;
if(d[i]+e[j].w<d[v]){
if(ever[v]) return true;
d[v]=d[i]+e[j].w;
if(dfs(v)) return true;
}
}
ever[i]=false;
return false;
}
int main(){
scanf("%d%d",&n,&m);
int x,a,b,c;
for(int i = 1;i<=m;i++){
scanf("%d",&x);
if(x==1){
scanf("%d%d%d",&a,&b,&c);
//a-b>=c
add(a,b,-c);
}
if(x==2){
scanf("%d%d%d",&a,&b,&c);
//a-b<=c;
add(b,a,c);
}
if(x==3){
scanf("%d%d",&a,&b);
add(a,b,0);
add(b,a,0);
}
}
for(int i = 1;i<=n;i++){
add(n+1,i,0);
}
fill(d+1,d+n+2,inf);
d[n+1]=0;
if(dfs(n+1)){
puts("No");
return 0;
}
puts("Yes");
return 0;
}
```