HDU 3572 网络源

HDU 3572 网络流

题意：

n个任务， m台机器(每台机器每天只能执行一个任务)  任务可以不连续执行，可以让别的机器交替执行

下面n行

need st en 表示任务需要在 [st, en]之间完成，需要need天 (保证 en - st+1 >=need )

问能否全部执行完

 

思路：

0为源点，1-n为n个任务  (源点到天数边权值为 need)

n+1 -  n+1+Maxday 为天数

每个任务到 [st, en]建权值为1的边

每个任务到汇点建权值为m的边

 

 

#include<string.h>
#include<stdio.h>
#include<queue>

#define M 1505
#define inf 33554432
using namespace std;

inline int Max(int a,int b){return a<b?b:a;}
inline int Min(int a,int b){return a>b?b:a;}

struct Edge{
    int from, to, cap, nex;
}edge[M*M];

int head[M*4], edgenum;
void addedge(int u, int v, int cap){
    Edge E = { u, v, cap, head[u]};
    edge[ edgenum ] = E;
    head[u] = edgenum ++;
}
int sign[M*4], s, t;
bool BFS(int from, int to){
    memset(sign, -1, sizeof(sign));
    sign[from] = 0;

    queue<int>q;
    q.push(from);
    while( !q.empty() ){
        int u = q.front(); q.pop();
        for(int i = head[u]; i!=-1; i = edge[i].nex)
        {
            int v = edge[i].to;
            if(sign[v]==-1 && edge[i].cap)
            {
                sign[v] = sign[u] + 1, q.push(v);
                if(sign[to] != -1)return true;
            }
        }
    }
    return false;
}
int Stack[M*4], top, cur[M*4];
int day;
int dinic(){

    int ans = 0;
    while( BFS(s, t) )
    {
        memcpy(cur, head, sizeof(head));
        int u = s;        top = 0;
        while(1)
        {
            if(u == t)
            {
                int flow = inf, loc;//loc 表示 Stack 中 cap 最小的边
                for(int i = 0; i < top; i++)
                    if(flow > edge[ Stack[i] ].cap)
                    {
                        flow = edge[Stack[i]].cap;
                        loc = i;
                    }

                    for(int i = 0; i < top; i++)
                    {
                        edge[ Stack[i] ].cap -= flow;
                        edge[Stack[i]^1].cap += flow;
                    }
                    ans += flow;
                    top = loc;
                    u = edge[Stack[top]].from;
            }
            for(int i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标
                if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;
            if(cur[u] != -1)
            {
                Stack[top++] = cur[u];
                u = edge[ cur[u] ].to;
            }
            else
            {
                if( top == 0 )break;
                sign[u] = -1;
                u = edge[ Stack[--top] ].from;
            }
        }
    }
    return ans == day;
}
void Have_map(int n, int m){
    day = 0;
    memset(head, -1, sizeof(head)); edgenum = 0;

    int i, j;
    int st, need, en, Maxday = 1;
    for(i = 1; i <= n; i++)
    {
        scanf("%d %d %d",&need,&st,&en);
        addedge(s, i, need);
        addedge(i, s, 0   );
        day += need;
        for(j = st; j <= en; j++)
        {
            addedge(i, n + 1 + j, 1);
            addedge(n + 1 + j, i, 0);
        }
        Maxday = Max(Maxday, en);
    }
    t = n + Maxday + 10;
    for(i = 1; i <= Maxday; i++)
    {
        addedge(n+i+1, t, m);
        addedge(t, n+i+1, 0);
    }
}
int main(){
    int n, m, T, Cas = 1;scanf("%d",&T);
    s = 0;
    while(T--)
    {
        scanf("%d %d", &n, &m);

        Have_map(n, m);
        printf("Case %d: ",Cas++);
        if(dinic())
            printf("Yes\n\n");
        else 
            printf("No\n\n");
    }
    return 0;
}