西安有哪些做网站的公司好/佛山全网营销推广

基础知识点

顶点活动（AOV）网是指用顶点表示活动，而用边集表示活动间优先关系的有向图。显然，图中不应当存在有向环，否则会让优先关系出现逻辑错误。

边活动（AOE）网是指用带权的边集表示活动，而用顶点表示事件的有向图，其中边权表示完成活动需要的时间。一般来说，AOE网用来表示一个工程的进行过程，而工程常常可以分为若干子工程（即“活动”），显然AOE网不应当有环，否则会出现和AOV网一样的逻辑问题。AOE网是基于工程提出的概念，主要着重解决两个问题：

1. 工程起始到终止至少需要多少时间
2. 哪些路径上的活动是影响整个工程进度的关键。

如果给定AOV网中各项顶点活动所需要的时间，那么可以将AOV网转换为AOE网。比较简单的方法是：将AOV网中每个顶点都拆分为两个顶点，分别表示活动的起点和终点，而两个顶点之间用有向边连接，该有向边表示原顶点的活动，边权给定；原AOV网中的边全部视为空活动，边权为0。

把入度为0的顶点叫做源点，出度为0的顶点叫做汇点。

一个AOE网络至少包含一个源点和一个汇点。

关键路径：从源点到汇点的路径长度最大的路径。

• 对于最早开始时间的初始化，如果题目没有特殊要求，那么所有结点都初始化为0。
• 对于最晚开始时间的初始化，如果题目没有特殊要求，那么汇点的最晚开始时间初始化为它的最早开始时间，其余结点初始化为INF。

求最长路径的方法

方法一

对于一个没有正环的图（指源点可达的正环，下同），如果需要求最长路径长度，则可以把所有边的边权乘以-1，令其变为相反数，然后使用Bellman-Ford算法或者SPFA算法求最短路径长度，将所得结果取反即可。

方法二

适用条件：给定一个有向无环图，求解整个图的所有路径中权值之和最大的那条。

采用动态规划+递归的方法，令dp[i]表示从i号顶点出发能获得的最长路径长度。

dp[i] = max{dp[j]+length[i-->j]}，其中j是i的后继结点

// dp[i]表示从i号顶点出发能获得的最长路径长度,  初始化为0
int DP(int i){if(dp[i]>0) return dp[i];  // dp[i]已计算得到for(int j=0;j<n;j++){  // 遍历结点i的所有出边if(G[i][j]!=INF){dp[i] = max(dp[i],DP(j)+G[i][j]);  // 用DP(j)的方式获取dp[j], 借助递归策略实现拓扑逆序的同等效果}}return dp[i];  // 返回计算完毕的dp[i]
}

POJ4109

题目大意：重新排列指令，以便CPU可以使用最短的时间完成所有指令

分析：

        若将指令的先后依赖关系抽象为有向边，则这个实际问题就转换为判断图上最长路径的长度，即关键路径的长度。可以根据拓扑序列逐一求出每个活动的最早开始时间，再根据拓扑序列的逆序列求出每个活动的最晚开始时间。所有活动中最早开始时间和最晚开始时间相同的活动为关键活动，而所有活动中最早开始时间的最大值便是关键路径的长度。

        值得注意的是，题目中指出每个指令的执行时间 为1ns，也就是说，所有源点的最早开始时间应该初始化为1，而非通常的0。

代码

#include <iostream>
#include <cstring>
#include <climits>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 1001;
const int INF = INT_MAX;
struct Edge{int to;  // 终点int length;  // 距离Edge(int t,int l):to(t),length(l){}
};
vector<Edge> graph[MAXN];
int earliest[MAXN];    // 最早开始时间
int latest[MAXN];    // 最晚开始时间
int inDegree[MAXN];   // 入度
void CriticalPath(int n){vector<int> topology;   // 拓扑序列queue<int> myQueue;for(int i=0;i<n;i++){if(inDegree[i]==0){myQueue.push(i);earliest[i] = 1;   // 初始化为1}}while(!myQueue.empty()){int u = myQueue.front();topology.push_back(u);myQueue.pop();for(int i=0;i<graph[u].size();i++){int v = graph[u][i].to;int length = graph[u][i].length;earliest[v] = max(earliest[v], earliest[u]+length);inDegree[v]--;if(inDegree[v]==0) myQueue.push(v);}}for(int i=topology.size()-1;i>=0;i--){int u = topology[i];if(graph[u].size()==0) latest[u] = earliest[u];   // 汇点的最晚开始初始化else latest[u] = INF;   // 非汇点的最晚开始初始化for(int j=0;j<graph[u].size();j++){int v = graph[u][j].to;int dd = graph[u][j].length;latest[u] = min(latest[u],latest[v]-dd);}}
}
int main(){int n,m;while(cin>>n>>m){memset(graph,0,sizeof(graph));for(int i=0;i<n;i++){earliest[i]=latest[i]=inDegree[i]=0;}while(m--){int from,to,length;cin>>from>>to>>length;graph[from].push_back(Edge(to,length));inDegree[to]++;}CriticalPath(n);int answer = 0;for(int i=0;i<n;i++){answer = max(answer,earliest[i]);}cout<<answer<<endl;}return 0;
}

论文（清华大学复试上机题）

代码

#include <iostream>
#include <cstring>
#include <climits>
#include <queue>
#include <vector>
using namespace std;
const int MAXN=1e5+1;
const int INF = INT_MAX;
const int MOD = 1e9+7;  // 这里没加
struct Edge {int to;long long length;Edge(int t,long long len):to(t),length(len) {}
};
vector<Edge> graph[MAXN];
long long inDegree[MAXN],earliest[MAXN],latest[MAXN],a[MAXN];
long long CriticalPath(int n) {vector<int> topology;queue<int> myQueue;for(int i=1; i<=n; i++) {if(inDegree[i]==0) {myQueue.push(i);}}while(!myQueue.empty()) {int u=myQueue.front();myQueue.pop();topology.push_back(u);for(int i=0; i<graph[u].size(); i++) {int v = graph[u][i].to;long long len = graph[u][i].length;inDegree[v]--;if(inDegree[v]==0) {myQueue.push(v);}earliest[v] = max(earliest[v],earliest[u]+len);}}long long totalTime=0;for(int i=1; i<=n; i++) {totalTime = max(totalTime,earliest[i]+a[i]);}for(int i=topology.size()-1; i>=0; i--) {int u=topology[i];if(graph[u].size()==0)latest[u] = totalTime - a[u];elselatest[u] = INF;for(int j=0; j<graph[u].size(); j++) {int v = graph[u][j].to;long long len = graph[u][j].length;latest[u] = min(latest[u],latest[v]-len);}}return totalTime;
}
int main() {int N,M;while(cin>>N>>M) {memset(graph,0,sizeof(graph));for(int i=1; i<=N; i++) { // 编号是1~N，而不是0~N-1inDegree[i] = latest[i] = earliest[i]=0;cin>>a[i];}for(int i=0; i<M; i++) {int from,to;cin>>from>>to;graph[from].push_back(Edge(to,a[from]));inDegree[to]++;}cout<<CriticalPath(N)<<endl;long long ans = 1;for(int i=1; i<=N; i++){ans *= (latest[i] - earliest[i] + 1);ans %= MOD;}cout<<ans<<endl;}return 0;
}