hdu4780 費用流 （機器任務工作不中斷問題）

hdu4780 費用流 （機器任務工作不中斷問題）

機器，任務 ，每個任務有有時間，不可中斷。

題意：m個機器，n個糖果要加工，給出每個糖果的工作時間（s,t），以及糖果之間、機器預備時間以及費用，求最小費用。

這題開始受原來可以時間中斷那題影響，開始用時間建圖，巨麻煩，後來學習了，才覺悟時間只是計算費用的，沒有幫毛錢關系， s-->機器-》糖果-》t;

因為要每個糖果都加工一次，糖果拆點，必經過（-inf）。有一個沒過，則無解。

網上的添加一組新點法也可以。我的使用釋放壓力+無窮碧流法也好。

跪點：注意！用inf=0x3f3f3f3f,最後加上n*inf,爆int! 這種以後要注意！順變 e[][3]也要longlong !

本來這樣我就A了！但是竟然因為一個變量的命名搞混了WA一天！！！SB了！ 自己搞變量不要搞這麼相似啊 ！！！！！！！！！！

#include
#include
#include
#include
#include
using namespace std;
const long long inf=0x3f3f3f3f;
const int maxn=505,maxe=80000;
int n,m,k;
int ss,tt;
int head[maxn];long long e[maxe][4];int nume=0;
void inline adde(int i, int j, int c,long long w)
{
    e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;
    e[nume][2]=c;e[nume++][3]=w;
    e[nume][0]=i;e[nume][1]=head[j];head[j]=nume;
    e[nume][2]=0;e[nume++][3]=-w;
}
int inq[maxn];long long d[maxn];int pre[maxn];int prv[maxn];
bool spfa(long long &sum)
{
    for(int i=0;i<=tt;i++)
       {
           inq[i]=0;d[i]=inf;
       }
    queueq;
    q.push(ss);
    inq[ss]=1;d[ss]=0;
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        inq[cur]=0;
        for(int j=head[cur];j!=-1;j=e[j][1])
        {
            int v=e[j][0];
            if(d[v]>d[cur]+e[j][3]&&e[j][2]>0)
            {
                d[v]=d[cur]+e[j][3];
                pre[v]=j;
                prv[v]=cur;
                if(!inq[v])
                {
                    q.push(v);
                    inq[v]=1;
                }
            }
        }
    }
    if(d[tt]==inf)return 0;
   int minf=inf;
    int cur=tt;
    while(cur!=ss)
    {
        minf=minfmac[i][1]+cgtime[i][j])
         {
             if(mac[i][1]+cgtime[i][j]<=mac[j][0])
             adde(i+m+n,j+m,1,cgmony[i][j]);
             else
             adde(i+n+m,j+m,1,cgmony[i][j]+k*(mac[i][1]+cgtime[i][j]-mac[j][0]));
         }
        }
     }
}
void init()
{
    nume=0;
    memset(head,-1,sizeof(head));
    ss=0,tt=m+n+n+1;
}
int main()
{

    while(~scanf("%d%d%d",&n,&m,&k)&&(n||m||k))
    {
        init();
        for(int i=1;i<=n;i++)
             scanf("%d%d",&mac[i][0],&mac[i][1]);

        for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++)
         {
             scanf("%d",&cmtime[i][j]);
         }
         for(int i=1;i<=n;i++)
           for(int j=1;j<=m;j++)
         {
             scanf("%d",&cmony[i][j]);
         }
         for(int i=1;i<=n;i++)
           for(int j=1;j<=n;j++)
         {
             scanf("%d",&cgtime[i][j]);
         }
        for(int i=1;i<=n;i++)
           for(int j=1;j<=n;j++)
         {
             scanf("%d",&cgmony[i][j]);
         }
        build();
        long long ans=mincost()+n*inf;
        if(ans>=inf)
         printf("-1\n");
        else
          printf("%I64d\n",ans);
    }
}