hdu3572Task Schedule 最大流

//n個任務，m台機器
//每個任務都有開始工作的時間，結束的時間和需要一台機器工作的天數
//每個任務的工作可以斷開，只需要在規定的時間內用機器工作規定天數
//在同一天，一個任務只能被一台機器工作
//問能否安排時間使得所有的任務都能在規定時間內完成
//對任務和其工作的時間建立權值為1的邊
//在建立一個超級源點和一個超級匯點
//從源點向任務引入權值為該任務需要工作的天數，從每一天向匯點建立權值為m的邊
//這樣從源點到匯點的最大流如果大於所有的任務的需要工作的天數之和，所有任務就能在規定時間完成
dinic算法：

#include
#include
#include
#include
using namespace std ;
const int maxn = 10010 ;
const int inf = 0x7fffffff ;
int st = 0 ;int en = 1001 ;
int dis[maxn];
struct Edge
{
    int v ;int next;
    int w ;
}edge[maxn*maxn] ;
int head[maxn] , nedge ;

void addedge(int u , int v , int w)
{
    edge[nedge].v = v ;
    edge[nedge].w = w ;
    edge[nedge].next = head[u] ;
    head[u] = nedge++ ;
    edge[nedge].v = u ;
    edge[nedge].w = 0 ;
    edge[nedge].next = head[v] ;
    head[v] = nedge++ ;
}
bool bfs()
{
    queue que ;
    memset(dis , -1 ,sizeof(dis)) ;
    dis[st] = 0 ;
    que.push(st) ;
    while(que.size())
    {
        int u = que.front() ;
        que.pop() ;
        for(int i = head[u]; i != -1 ; i = edge[i].next)
        {
            int v = edge[i].v ;
            if(edge[i].w > 0 && dis[v] < 0)
            {
                dis[v] = dis[u] + 1 ;
                que.push(v) ;
            }
        }
    }
    if(dis[en] > 0)
    return true ;
    return false ;
}
int dfs(int x,int mx)
{
    if(x==en)
    return mx;
    int i;
    int ans=0;
    int a;
    for(i=head[x];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(dis[v]==dis[x]+1&&edge[i].w>0&&(a=dfs(v,min(mx,edge[i].w))))
        {
            edge[i].w -= a;
            edge[i^1].w += a;
            ans += a;
            mx -= a;
            if(!mx)
            break;
        }
    }
    if(!ans)
    dis[x] = -1; //dinic算法的主要優化
    return ans;
}

int main()
{
    //freopen(in.txt , r ,stdin) ;
    int t  ; int cas = 0 ;
    int n , m ;
    scanf(%d , &t) ;
    while(t--)
    {
        scanf(%d%d , &n , &m) ;
        int sum = 0 ;
        memset(head ,-1 , sizeof(head)) ;
        nedge = 0 ;
        int ma = 0 ;int mi = inf ;
        for(int i = 1;i <= n;i++)
        {
            int si , ei , pi ;
            scanf(%d%d%d ,&pi , &si , &ei) ;
            addedge(st , i , pi) ;
            sum += pi ;
            for(int j = si;j <= ei ;j++)
            addedge(i , j + 500, 1) ;
        }
        for(int j = 501 ;j <= 1000;j++)
        addedge(j , en , m) ;
        int res ;int ans = 0 ;
        while(bfs())
          while(res = dfs(st , inf))
            ans += res ;
        printf(Case %d: ,++cas) ;
        if(ans >= sum)
        puts(Yes) ;
        else puts(No);
        puts() ;
    }
    return  0 ;
}

isap算法：

#include
#include
#include
#include
using namespace std ;
const int maxn = 10010 ;
const int inf = 0x7fffffff ;
int st = 0 ;int en = 1001 ;    int n , m ;
int dis[maxn];int gap[maxn] ,cur[maxn],pre[maxn] ;
struct Edge
{
    int v ;int next;
    int w ;
}edge[maxn*maxn] ;
int head[maxn] , nedge ;
void addedge(int u , int v , int w)
{
    edge[nedge].v = v ;
    edge[nedge].w = w ;
    edge[nedge].next = head[u] ;
    head[u] = nedge++ ;
    edge[nedge].v = u ;
    edge[nedge].w = 0 ;
    edge[nedge].next = head[v] ;
    head[v] = nedge++ ;
}
void bfs()
{
    memset(dis, -1 , sizeof(dis)) ;
    memset(gap , 0 , sizeof(gap)) ;
    queue que ;
    dis[en] = 0 ; gap[0]++ ;
    que.push(en) ;
    while(que.size())
    {
        int u = que.front() ;que.pop() ;
        for(int i = head[u] ; i != -1 ;i =  edge[i].next)
        {
            int v = edge[i].v ;
            if(dis[v] < 0 && edge[i^1].w > 0)
            {
                dis[v] = dis[u] + 1 ;
                gap[dis[v]]++ ;
                que.push(v) ;
            }
        }
    }
}
int isap()
{
    bfs() ;
    memset(pre , -1 , sizeof(pre)) ;
    memcpy(cur , head, sizeof(head)) ;
    int u = pre[st] = st ;
    gap[0] = n ;
    int  maxflow =0 ;
    int aug = inf ;bool flag  ;
    while(dis[st] < n)
    {
        flag = false ;
        for(int i = cur[u] ;i != -1 ;i = edge[i].next)
        {
            int v = edge[i].v ;
            if(dis[u] == dis[v] + 1 && edge[i].w > 0)
            {
                flag = true ;
                cur[u] = i ;
                pre[v] = u ; u = v ;
                aug = min(aug , edge[i].w) ;
                if(v == en)
                {
                    maxflow += aug ;
                    for(u = pre[v] ; ; u = pre[u])
                    {
                        edge[cur[u]].w -= aug ;
                        edge[cur[u]^1].w += aug ;
                        if(u == st)break;
                    }
                    aug = inf ;
                }
                break ;
            }
        }
        if(flag)continue ;
        int mi = n;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(dis[v] < mi && edge[i].w > 0)
            {
                mi=dis[v];
                cur[u]=i;
            }
        }
        if((--gap[dis[u]]) == 0)break ;
        dis[u] = mi + 1 ;
        gap[dis[u]]++ ;
        u = pre[u] ;
    }
    return maxflow ;
}
int main()
{
   // freopen(in.txt , r ,stdin) ;
    int t  ; int cas = 0 ;
    scanf(%d , &t) ;
    while(t--)
    {
        scanf(%d%d , &n , &m) ;
        int sum = 0 ;
        memset(head ,-1 , sizeof(head)) ;
        nedge = 0 ;
        int ma = 0 ;int mi = inf ;
        for(int i = 1;i <= n;i++)
        {
            int si , ei , pi ;
            scanf(%d%d%d ,&pi , &si , &ei) ;
            addedge(st , i , pi) ;
            sum += pi ;
            for(int j = si;j <= ei ;j++)
            addedge(i , j + 500, 1) ;
        }
        for(int j = 501 ;j <= 1000;j++)
        addedge(j , en , m) ;
        int res ;int ans = 0 ;
        n = n + 2 + 500 ;
        ans = isap() ;
        printf(Case %d: ,++cas) ;
        if(ans >= sum)
        puts(Yes) ;
        else puts(No);
        puts() ;
    }
    return  0 ;
}