POJ-1716 同上..SPFA差分约束..

题意和POJ1201相似..但更简单..就是说 a 到 b 至少有两个数...问整个集合最少需要多少元素...

约束条件也就是 Sb - S(a-1) >=2...同POJ1201的构图和解法就是了...

Program :

#include#include#define oo 0x7F#define MAXN 30001using namespace std;struct p1{ int x,y,k,next; }line[MAXN];int n,m,link[MAXN],x,y,minnum,maxnum,i;queue myqueue;int SPFA(){ int i,k,h,d[MAXN]; bool used[MAXN]; while (!myqueue.empty()) myqueue.pop(); memset(d,-oo,sizeof(d)); memset(used,false,sizeof(used)); d[minnum]=0; myqueue.push(minnum); while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); used[h]=false; k=link[h]; while (k) { if (d[line[k].y]maxnum) maxnum=y; m++; line[m].x=x; line[m].y=y; line[m].k=2; line[m].next=link[line[m].x]; link[line[m].x]=m; } for (i=minnum;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。