本文主要是介绍cf 164 C 费用流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给你n个任务，k个机器，n个任务的起始时间，持续时间，完成任务的获利
每个机器可以完成任何一项任务，但是同一时刻只能完成一项任务，一旦某台机器在完成某项任务时，直到任务结束，这台机器都不能去做其他任务
最后问你当获利最大时，应该安排那些机器工作，即输出方案
具体建图方法：
新建源汇S T‘
对任务按照起始时间s按升序排序
拆点：
u 向 u'连一条边 容量为 1 费用为 -c,
u' 向 T连一条边 容量为 inf 费用为 0；
如果任务u完成后接下来最先开始的是任务v
则从u' 向 v连一条边，容量inf 费用 0.
另外，任务从前往后具有传递性，所以必须是第i个任务向第i+1个任务建边，容量为inf
最后，限制一下起始点向第一个任务的流量即可（即K）
const int maxn = 5000 ;
const int maxm = 50000 ;
const int inf = 1000000000 ;
struct Edge{int v , f , w , next ;int u ;Edge(){}Edge(int _v , int _f , int _w , int _next):v(_v),f(_f),w(_w),next(_next){}
};
int g[maxn + 10] ;
Edge e[maxm + 10] ;
int source , meet ;
int id ;void add(int u , int v , int f , int w){e[++id] = Edge(v , f , w , g[u]) ;e[id].u = u ;g[u] = id ;e[++id] = Edge(u , 0 , -w , g[v]) ;e[id].u = v ;g[v] = id ;
}queue<int> que ;
bool in[maxn + 10] ;
int dist[maxn + 10] ;
int pv[maxn + 10] , pe[maxn + 10] ;int bfs(){while(! que.empty()) que.pop() ;que.push(source) ;memset(dist , 63 , sizeof(dist)) ;dist[source] = 0 ;in[source] = 1 ;while(! que.empty()){int u = que.front() ; que.pop() ;in[u] = 0 ;for(int i = g[u] ; i ; i = e[i].next){int v = e[i].v ;if(e[i].f > 0 && dist[u] + e[i].w < dist[v]){dist[v] = dist[u] + e[i].w ;pv[v] = u ;pe[v] = i ;if(! in[v]){in[v] = 1 ; que.push(v) ;}}}}return dist[meet] < inf ;
}int augment(){int u = meet ;int delta = inf ;while(u != source){delta = min(delta , e[pe[u]].f) ;u = pv[u] ;}u = meet ;while(u != source){e[pe[u]].f -= delta ;e[pe[u] ^ 1].f += delta ;u = pv[u] ;}return dist[meet] * delta ;
}int mincostflow(){int ans = 0 ;while(bfs()) ans += augment() ;return ans ;
}void init(){memset(g , 0 , sizeof(g)) ;id = 1 ;
}struct Task{int s , e , val , id ;friend bool operator < (const Task A , const Task B){return A.s < B.s ;}
}tk[1008] ;
int ans[1008] ;int main(){int n , k , i , j , u , v ;while(cin>>n>>k){for(i = 1 ; i <= n ; i++){scanf("%d%d%d" , &tk[i].s , &tk[i].e , &tk[i].val) ;tk[i].e = tk[i].s + tk[i].e - 1 ;tk[i].id = i ;}sort(tk+1 , tk+1+n) ;init() ;source = 0 , meet = 2*n + 1 ;for(i = 1 ; i <= n ; i++){add(i , i+n , 1 , -tk[i].val) ;add(i+n , meet , inf , 0) ;for(j = i + 1 ; j <= n ; j++){if(tk[i].e < tk[j].s){add(i+n , j , inf , 0) ;break ;}}if(i < n) add(i , i+1 , inf , 0) ;}add(source , 1 , k , 0) ;add(n , meet , k , 0) ;mincostflow() ;memset(ans , 0 , sizeof(ans)) ;for(i = 2 ; i <= id ; i+=2){u = e[i].u , v = e[i].v ;if(e[i].f == 0){if(u != source && v != meet && u <= n)ans[tk[u].id] = 1 ;}}for(i = 1 ; i <= n ; i++)printf("%d " , ans[i]) ;puts("") ;}return 0 ;
}这篇关于cf 164 C 费用流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
