uva11478 Halum【二分+差分约束】

WA了半个礼拜的题终于找到错在哪了==

先说题意：对于给定有向图，定义一种操作：对于选定的某一点，进入这个点的所有边权都减去d,从这个点出去的所有边权都加上d。经过一系列的操作，使得所有边权的最小值达到最大，需保证这个最值是正数==

既然是差分约束，需要记得把点当做最短路的点假设每个点都有一个点权sum(a)，而w(a,b)+sum(a)-sum(b)>=x，x是所有边权的最小值，把边权sum放到等号右边，就构成了差分约束的不等式组，，保证不出现负环的spfa就是最大的x求得的。

再说我错在哪了，对于这个题来说，要人为加一个超级源点，（就像网络流一样，没有固定的源点汇点，就要人为添加）我就是因为没有这句话还觉得自己二分或者模板错了orz 要是不想加源点，spfa模板最开始push的点就是1-n都加进去，dist[]都是0

#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int inf=0x3f3f;
const int maxn=505;
int n,m;
struct Edge
{
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[maxn];
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}
bool vis[maxn];
int cnt[maxn];
int dist[maxn];
bool spfa(int start,int n)
{
    memset(vis,false,sizeof(vis));
    memset(dist,inf,sizeof(dist));
    vis[start]=true;
    dist[start]=0;
    queue<int>que;
    while(!que.empty()) que.pop();
    que.push(start);
    memset(cnt,0,sizeof(cnt));
    cnt[start]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=0;i<E[u].size();i++)
        {
            int v=E[u][i].v;
            if(dist[v]>dist[u]+E[u][i].cost)
            {
                dist[v]=dist[u]+E[u][i].cost;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>n) return false;
                }
            }
        }
    }
    return true;
}
bool judge(int x)
{
   // cout<<"rrr"<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<E[i].size();j++)
            E[i][j].cost-=x;
    }
    bool flag=spfa(0,n);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<E[i].size();j++)
            E[i][j].cost+=x;
    }
    return flag;
}
    int main()
    {
        //freopen("cin.txt","r",stdin);
       // int cas=1;
       // scanf("%d",&t);
        while(~scanf("%d%d",&n,&m))
        {
           // printf("Case #%d: ",cas++);
            for(int i=0;i<=n;i++) E[i].clear();
        //    memset(head,-1,sizeof(head));
            int l=1,mid,r=-inf;
            while(m--)
            {
                int a,b;
                int c;
                scanf("%d%d%d",&a,&b,&c);
                addedge(a,b,c);
                if(c>r)r=c;
            }
            for(int i=1;i<=n;i++)addedge(0,i,0);
          //  cout<<"rrr"<<endl;
           // printf("r=%d\n",r);
            if(judge(r))
            {
                printf("Infinite\n");
                continue;
            }
            else if(!judge(1))
            {
                puts("No Solution");
                continue;
            }
            int ans;
            while(l<=r)
            {
                mid=(l+r)/2;
               // cout<<mid<<endl;
               // printf("l=%d,mid=%d,r=%d    ",l,mid,r);
                if(judge(mid)) ans=mid,l=mid+1;
                else {r=mid-1;}
               // printf("l=%d,mid=%d,r=%d,ans=%d\n",l,mid,r,ans);
            }
            printf("%d\n",ans);
        }
        return 0;
    }