http://poj.org/problem?id=1201
题意是给你n个区间，每个区间有一个边界[a,b],以及一个整数c
要满足每个区间[a,b]都至少有c个元素
解题方法就是构造差分约束公式
(a-1)-b<=-c
建立一条边从b到a-1，权值为-c
然后还要加上两个条件
(i+1)-i>=0 -> i-(i+1)<=0
(i+1)-i<=1
建立i+1 到 i 权值为 0的边
建立i到i+1 权值为1的边
跑一边spfa就解决
#include <cstdio> #include<cstring> #include<iostream> #include<queue> using namespace std; #define N 50005 #define M 500009 const int inf=0x3f3f3f3f; int dis[N],head[N]; queue<int> q; int tot; bool vis[N]; struct Edge { int from,to,cost,next; } edge[M]; void add(int u,int v,int w) { edge[tot].from=u; edge[tot].to=v; edge[tot].cost=w; edge[tot].next=head[u]; head[u]=tot++; } void spfa(int u) { memset(dis,inf,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[u]=0; q.push(u); vis[u]=1; while(!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for(int i=head[x]; ~i; i=edge[i].next) { int y=edge[i].to; if(dis[x]+edge[i].cost<dis[y]) { dis[y]=dis[x]+edge[i].cost; if(!vis[y]) vis[y]=1,q.push(y); } } } } void init() { memset(head,-1,sizeof(head)); tot=0; } int main() { int n; while(~scanf("%d",&n)) { init(); int a,b,w; int mina=1e9,maxb=-mina; for (int i=0; i<n ; i++ ) { scanf("%d%d%d",&a,&b,&w); a++; b++; add(b,a-1,-w); mina=min(mina,a); maxb=max(maxb,b); } for (int i=mina-1; i<maxb ; i++ ) { add(i+1,i,0); add(i,i+1,1); } int s=maxb; int t=mina-1; spfa(s); printf("%d",-dis[t]); } return 0; }
https://cn.vjudge.net/problem/POJ-2983
题意给点n个点m条有向边
如果输入P则改边长度确定，如果输入V则改边长度大于等于1
问是否满足所有的条件
将确定边的条件设为
1<=(u,v)<=1
不确定边的条件设为
(u,v)>=1 -> (v,u)<=-1
并且建立一个超级源点0指向所有点
跑一边spfa，出现负环则说明矛盾.
#include <cstdio> #include<cstring> #include<iostream> #include<queue> using namespace std; #define N 50005 #define M 500009 const int inf=0x3f3f3f3f; int dis[N],head[N]; int fax[N]; int n,m; queue<int> q; int tot; bool vis[N]; struct Edge { int from,to,cost,next; } edge[M]; void add(int u,int v,int w) { edge[tot].from=u; edge[tot].to=v; edge[tot].cost=w; edge[tot].next=head[u]; head[u]=tot++; } bool spfa(int u) { memset(dis,inf,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[u]=0; q.push(u); vis[u]=1; while(!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for(int i=head[x]; ~i; i=edge[i].next) { int y=edge[i].to; if(dis[x]+edge[i].cost<dis[y]) { dis[y]=dis[x]+edge[i].cost; if(!vis[y]) { fax[y]++; vis[y]=1; q.push(y); if(fax[y]>n) return false; } } } } return true; } void init() { memset(head,-1,sizeof(head)); memset(fax,0,sizeof(fax)); tot=0; } int main() { while(~scanf("%d %d",&n,&m)) { getchar(); init(); for (int i=1;i<=n ;i++ ) add(0,i,0); int a,b,w; for (int i=0; i<m ; i++ ) { char ch=getchar(); if(ch=='P') { scanf(" %d %d %d",&a,&b,&w); add(a,b,w); add(b,a,-w); } else { scanf(" %d %d",&a,&b); add(b,a,-1); } getchar(); } if(spfa(0)) { printf("Reliable "); } else { printf("Unreliable "); } } return 0; }