hdu 1384 查分约束

#include<stdio.h>

/*

要善于挖掘隐含条件

dis[v]-dis[u]>=bian[i].w;一个条件(u,v,bian[i].w);

dis[i+1]>=dis[i];隐含条件(i,i+1,0);

dis[i+1]-dis[i]<=1即dis[i]>=dis[i+1]-1;(i+1,i,-1);

>=求最大约束条件，求最长路.

<=求最小约束条件，求最短路.

*/

#include<string.h>

#include<queue>

using namespace std;

#define N  51000

#define inf 0x3fffffff

struct node {

int u,v,w,next;

}bian[N*4];

int head[N],yong;

void addedge(int u,int v,int w) {

bian[yong].u=u;

bian[yong].v=v;

bian[yong].w=w;

bian[yong].next=head[u];

head[u]=yong++;

}

int spfa(int s,int t) {

int dis[N];

queue<int>q;

int visit[N],i;

for(i=s;i<=t;i++)

    dis[i]=-inf;

memset(visit,0,sizeof(visit));

visit[s]=1;

dis[s]=0;

q.push(s);

while(!q.empty()) {

    int u=q.front();

    q.pop();

    visit[u]=0;

   for(i=head[u];i!=-1;i=bian[i].next) {

    int v=bian[i].v;

    if(dis[v]<dis[u]+bian[i].w) {

        dis[v]=dis[u]+bian[i].w;

        if(!visit[v]) {

            visit[v]=1;

            q.push(v);

        }

    }

   }

}

return dis[t];

}

int main()

{

    int n,i,j,k,minn,maxx;

    while(scanf("%d",&n)!=EOF)

    {

        minn=inf;

        maxx=-1;

        memset(head,-1,sizeof(head));

        yong=0;

        while(n--)

        {

            scanf("%d%d%d",&i,&j,&k);

            addedge(i,j+1,k);

            if(j+1>maxx)maxx=j+1;

            if(i<minn)minn=i;

        }

        for(i=minn; i<=maxx; i++)

           addedge(i,i+1,0),addedge(i+1,i,-1);//

       printf("%d\n",spfa(minn,maxx));

        }

    return 0;

}
巴特西

hdu 1384 查分约束

最新文章

热门文章
