poj 1275 Cashier Employment 差分約束

poj 1275 Cashier Employment 差分約束

差分約束模板題，差分約束是判斷聯立不等式組是否有解的一種方法,建圖是關鍵。

代碼：

//poj 1275
//sep9
#include 
#include 
using namespace std;
const int maxM=10024;
const int maxN=32;

struct Edge
{
	int v,w,nxt;	
}edge[maxM];
int t[maxN],c[maxN],head[maxN],vis[maxN],inq[maxN],dis[maxN];
int e;

void addedge(int u,int v,int w)
{
	edge[e].v=v;edge[e].w=w;edge[e].nxt=head[u];
	head[u]=e++;	
}

bool spfa()
{
	memset(inq,0,sizeof(inq));
	for(int i=0;i<=24;++i) dis[i]=INT_MIN;
	memset(vis,0,sizeof(vis));
	queue Q;
	Q.push(0);
	dis[0]=0;
	inq[0]=1;
	vis[0]=1;
	while(!Q.empty()){
		int u=Q.front();Q.pop();inq[u]=0;
		for(int i=head[u];i!=-1;i=edge[i].nxt){
			int v=edge[i].v,w=edge[i].w;
			if(dis[v]=25)
						return false;
				}	
			}
		}
	}	
	return true;
}

int main()
{
	int cases;
	scanf("%d",&cases);
	while(cases--){
		memset(head,-1,sizeof(head));
		memset(t,0,sizeof(t));
		for(int i=1;i<=24;++i)
			scanf("%d",&c[i]);
		int n;
		scanf("%d",&n);	
		for(int i=0;i