任务调度跟最小生成树
任务调度和最小生成树
调度问题：
问题背景：一个共享资源，多个job要访问。
question：那我们应该如何排列job的顺序
假定：每个job 有优先级 ，和需要使用资源的时间长度当我们排列所有job之后，每个job都会有一个开始时间和结束时间，那么如何评定一个方案是不是好方案 ,/[ c_{i} /] 指的是任务最后完成时间
/[ \min \left( \sum_{i=1}^{n}c_{i}w_{i}\right) /]
ok 那么，我们的算法就需要解决上述问题：贪心
原始博客地址
#include<string>
#include<iostream>
#include<fstream>
#include <map>
#include <queue>
//#include <deque>
using namespace std;
ifstream fin("jobs.txt");
struct Job{
int w;
int l;
bool operator < (const Job & n)const {
if( (w - l) == (n.w - n.l) ) return w > n.w;
return (w - l) > (n.w - n.l);
//return (w *1.0/ l) > (n.w *1.0/ n.l);
}
};
const int N = 10000 + 10;
struct Job data[N];
int input()
{
int n;
fin >>n ;
for(int i = 1 ; i <= n ; i ++){
fin>>data[i].w >>data[i].l;
}
return n;
}
void jobs1()
{
int n = input();
sort(data+ 1 ,data + n + 1);
long long sum = 0;
int l = 0;
for(int i = 1 ; i <= n ; i ++){
l += data[i].l ;
sum += l * data[i].w;
}
cout << sum << endl;
}
2: 最小生成树
证明：
引入割的定义：
G=<V,E> ，V是G的顶点集，那么割是对（S,V-S)的一个划分，当一条边e(u,v),其中一个端点属于S，另一个属于V-S。那么这条边是割的边。
cut 对于最小生成树的帮助是，如果某条边是cut（S,V-S）中最小的，那么这条边一定是属于最小生成树里面的。
如果某割是两个子图之间权值最小的边，那么他一定在最小生成树里面。
for(int i = 1 ; i < n ; i ++){
int mindist = 0x33fffff;
// get min
for(int j = 1 ; j <= n ; j ++){
if(used[j] == 0){
if(dist[j] < mindist){
mindist = dist[j];
pos = j;
}
}
}//end for
ans += mindist;
used[pos] = 1;
for(int j = 1 ; j <= n ; j ++){
if(used[j] == 0){
if(dist[j] > mat[pos][j])
dist[j] = mat[pos][j];
}
}
}