實驗一
實驗?zāi)康呐c要求：理解分治法的基本思想和設(shè)計方法。
實驗題目：
1.實現(xiàn)基于分治法的歸并排序算法.
#include <iostream>
using namespace std;
void merge(int *data, int p, int q, int r)
{
int n1, n2, i, j, k;
int *left=NULL, *right=NULL;
n1 =q-p+1;
n2 =r-q;
left = (int *)malloc(sizeof(int)*(n1));
right = (int *)malloc(sizeof(int)*(n2));
for(i=0; i<n1; i++) //對左數(shù)組賦值
left[i] = data[p+i];
for(j=0; j<n2; j++) //對右數(shù)組賦值
right[j] = data[q+1+j];
i =j=0;
k=p;
while(i<n1&&j<n2) //將數(shù)組元素值兩兩比較，并合并到data數(shù)組
{
if(left[i]<=right[j])
data[k++]=left[i++];
else
data[k++] = right[j++];
}
for(;i<n1;i++) //如果左數(shù)組有元素剩余，則將剩余元素合并到data數(shù)組
data[k++] = left[i];
for(;j<n2;j++) //如果右數(shù)組有元素剩余，則將剩余元素合并到data數(shù)組
data[k++] = right[j];
}
void merge_Sort(int *data, int p, int r)
{
int q;
if(p<r) //只有一個或無記錄時不須排序
{
q = (int)((p+r)/2); //將data數(shù)組分成兩半
merge_Sort(data, p, q); //遞歸拆分左數(shù)組
merge_Sort(data, q+1, r); //遞歸拆分右數(shù)組
merge(data, p, q, r); //合并數(shù)組
}
}
void merge_sort(int a[],const int size)
{
merge_Sort(a,0,size-1);
}
void main()
{
int count=7;
int a[]={1,3,2,4,5,1,2};
merge_sort(a,count); //排序
for(int i=0;i<count;i++)
cout<<a[i]<<" ";
}
2.實現(xiàn)快速排序的算法,并嘗試采用不同的方法實現(xiàn)線性的劃分過程.
#include <iostream>
using namespace std;
void quick_sort(int a[], int left, int right)
{
if(left<right)
{
int i = left;
int j = right;
int x = a[i];
while(i<j)
{
while(i<j&&a[j]>x)
j--;
if(i<j){
a[i] = a[j];
i++;
}
while(i<j&&a[i]<x)
i++;
if(i<j){
a[j] = a[i];
j--;
}
}
a[i] = x;
quick_sort(a, left, i-1);
quick_sort(a, i+1, right);
}
}
void main()
{
int a[]={1,2,3,4,5,8,6,1};
int size=8;
quick_sort(a,0,size-1);
for(int i=0;i<size;i++)
cout<<a[i]<<" ";
}
3.有一個數(shù)的序列A[1]、A[2] 、A[3] 、…… 、A[n]，若i<j，并且A[i]>A[j]，則稱A[i]與A[j]構(gòu)成了一個逆序?qū)?，設(shè)計算法求數(shù)列A中逆序?qū)Φ膫€數(shù).
#include <iostream>
using namespace std;
int merge(int *data, int p, int q, int r)
{
int n1, n2, i, j, k;
int *left=NULL, *right=NULL;
int count=0;
n1 =q-p+1;
n2 =r-q;
left = (int *)malloc(sizeof(int)*(n1));
right = (int *)malloc(sizeof(int)*(n2));
for(i=0; i<n1; i++) //對左數(shù)組賦值
left[i] = data[p+i];
for(j=0; j<n2; j++) //對右數(shù)組賦值
right[j] = data[q+1+j];
i =j=0;
k=p;
while(i<n1&&j<n2) //將數(shù)組元素值兩兩比較，并合并到data數(shù)組
{
if(left[i]<=right[j])
data[k++]=left[i++];
else
{
count=count+n1-i;
data[k++] = right[j++];
}
}
for(;i<n1;i++) //如果左數(shù)組有元素剩余，則將剩余元素合并到data數(shù)組
{
data[k++] = left[i];
}
for(;j<n2;j++) //如果右數(shù)組有元素剩余，則將剩余元素合并到data數(shù)組
data[k++] = right[j];
return count;
}
int merge_Sort(int *data, int p, int r)
{
int count1,count2,count3,count=0;
int q;
if(p<r) //只有一個或無記錄時不須排序
{
q = (int)((p+r)/2); //將data數(shù)組分成兩半
count1=merge_Sort(data, p, q); //遞歸拆分左數(shù)組
count2=merge_Sort(data, q+1, r); //遞歸拆分右數(shù)組
count3=merge(data, p, q, r); //合并數(shù)組
count=count1+count2+count3;
}
return count;
}
int merge_sort(int a[],const int size)
{
int count = merge_Sort(a,0,size-1);
return count;
}
void main()
{
int size=7;
int a[]={1,3,7,8,5,1,7};
int count=merge_sort(a,size); //排序
for(int i=0;i<size;i++)
cout<<a[i]<<" ";
cout<<endl<<"逆序?qū)?shù)："<<count<<endl;
}
4.(選做題) 引入逆序計數(shù)問題作為考察兩個序列有多大差別的一個好的度量指標。但是人們可能感覺這個量度太敏感了。如果i<j，并且A[i]>2A[j]，我們把這對i,j叫做重要的逆序。設(shè)計一個O(nlogn) 的算法計數(shù)在兩個序列中的重要逆序個數(shù)。
實驗二
實驗?zāi)康呐c要求：理解分治法的基本思想和設(shè)計方法。
實驗題目：
1.k-路合并操作問題：假定有k個有序數(shù)組，每個數(shù)組中含有n個元素，您的任務(wù)是將它們合并為單獨的一個有序數(shù)組，該數(shù)組共有kn個元素。設(shè)計和實現(xiàn) 一個有效的分治算法解決k-路合并操作問題，并分析時間復(fù)雜度。
#include <iostream>
using namespace std;
#define LEN 10 //最大歸并段長
#define MINKEY -1 //默認全為正數(shù)
#define MAXKEY 100 //最大值,當(dāng)一個段全部輸出后的賦值
struct Array
{
int arr[LEN];
int num;
int pos;
}*A;
int k,count;
int *LoserTree,*External;
void Adjust(int s)
{
int t=(s+k)/2;
int temp;
while(t>0)
{
if(External[s] > External[LoserTree[t]])
{
temp = s;
s = LoserTree[t];
LoserTree[t]=temp;
}
t=t/2;
}
LoserTree[0]=s;
}
void CreateLoserTree()
{
External[k]=MINKEY;
int i;
for(i=0;i<k;i++)LoserTree[i]=k;
for(i=k-1;i>=0;i--)Adjust(i);
}
void K_Merge()
{
int i,p;
for(i=0;i<k;i++)
{
p = A[i].pos;
External[i]=A[i].arr[p];
//cout<<External[i]<<",";
A[i].pos++;
}
CreateLoserTree();
int NO = 0;
while(NO<count)
{
p=LoserTree[0];
cout<<External[p]<<",";
NO++;
if(A[p].pos>=A[p].num)External[p]=MAXKEY;
else
{
External[p]=A[p].arr[A[p].pos];
A[p].pos++;
}
Adjust(p);
}
cout<<endl;
}
int main()
{
freopen("in.txt","r",stdin);
int i,j;
count=0;
cin>>k;
A=(Array *)malloc(sizeof(Array)*k);
for(i=0;i<k;i++)
{
cin>>A[i].num;
count=count+A[i].num;
for(j=0;j<A[i].num;j++)
{
cin>>A[i].arr[j];
}
A[i].pos=0;
}
LoserTree=(int *)malloc(sizeof(int)*k);
External=(int *)malloc(sizeof(int)*(k+1));
K_Merge();
return 0;
}
附件-文件in.txt
5
1 5 6 8 25
6
2 6 9 25 30 32
3
5 9 16
6
6 9 15 24 30 36
2
8 34
2.Split操作的要求是：以一個數(shù)組s和一個值v為輸入，將數(shù)組s劃分成3個子集：比v小的元素組成的集合，等于v的元素組成的集合以及比v大的元素組成的集合。設(shè)計和實現(xiàn)一種O(n)的就地split算法，即該算法不額外分配新的內(nèi)存。
#include <iostream>
#include <VECTOR>
using namespace std;
void Split(std::vector< int > &array,const int value)
{
int length=array.size();
int i=0,j=length-1;
while(i<j)
{
while(array[i]<=value)
++i;
if((i<j))
std::swap(array[i],array[j--]);
}
int max_pot=i;
i=0;
cout<<endl<<max_pot<<endl;
for(int i=0;i < array.size();++i)
cout<<array[i]<<" ";
while(i<j)
{
while(array[i]<value)
++i;
while(array[j]>=value)
--j;
if((array[i]==value)&&(i<j))
std::swap(array[i++],array[j--]);
}
int min_pot=i;
}
int main()
{
int a[20]={1,3,4,2,5,5,5,7,9,19,4,6,5,7,23,3,4,5,8,12};
vector<int> array(a,a+20);
cout<<"Testing Data:\n";
for(int i=0;i < array.size();++i)
cout<<array[i]<<" ";
Split(array,5);
cout<<"\nOutput:\n";
for(int i=0;i < array.size();++i)
cout<<array[i]<<" ";
return 0;
}
實驗三
實驗?zāi)康呐c要求：理解分治法的基本思想和設(shè)計方法。
實驗題目：
1.尋找中項
【問題描述】
對于長度為n的整型數(shù)組A，隨機生成其數(shù)組元素值，然后實現(xiàn)一個線性時間的算法，在該數(shù)組中查找其中項。
#include<iostream>
#include<stdio.h>
#include <vector>
#include <time.h>
#include <stdlib.h>
int searchMed(std::vector<int>& arr);
int* split(std::vector<int>& arr_s,int m_begin,int m_end);
int select(std::vector<int>& arr_s,int k,int m_begin,int m_end);
int main()
{
std::vector<int> arr={2,3,1,4,1,5,5,6};
int r=searchMed(arr);
std::cout<<r;
return 0;
}
int searchMed(std::vector<int>& arr){
//選出v s split
//選出k 剛開始是size/2 后來是(size-...)/2
int r=select(arr,arr.size()/2,0,arr.size()-1);
return r;
}
int* split(std::vector<int>& arr_s,int m_begin,int m_end){
// TODO 把數(shù)組段第一個數(shù)劃分，并返回中間值的下標
int a[2];
int k=arr_s[m_begin];
while (m_begin < m_end)
{
while (m_begin < m_end && arr_s[m_end] > k)
m_end--;
if (m_begin < m_end)
arr_s[m_begin++] = arr_s[m_end];
while (m_begin < m_end && arr_s[m_begin] < k)
m_begin++;
if (m_begin < m_end)
arr_s[m_end--] = arr_s[m_begin];
}
arr_s[m_begin] = k;
a[0]= m_begin; a[1] = m_end;
while (arr_s[a[0] - 1] == k)
{
a[0]--;
}
while (arr_s[a[1] + 1] ==k)
{
a[1]++;
}
return a;//==的兩邊位置
}
int select(std::vector<int>& arr_s,int k,int m_begin,int m_end){
//S< S=
int item;
if (m_end - m_begin < 2)
{
if (arr_s[m_begin] <arr_s[m_end])
item = k == m_begin ? arr_s[m_begin] : arr_s[m_end];
else
item = k == m_end ? arr_s[m_end] : arr_s[m_begin];
return item;
}
int s1,s2;//s1是＜v的數(shù)的最后一個位置 s2是等于v的數(shù)的最后一個位置
//srand( (unsigned)time( NULL ) );
// int v= arr_s[rand()%arr_s.size()];
int* a;
a=split(arr_s,m_begin,m_end);//return s1,s2
s1=a[0];
s2=a[1];
if(k<s1)
item=select(arr_s,k,m_begin,s1-1);
else
if (k>=s1&&k<=s2)
item=arr_s[s2];
else item=select(arr_s,k,s2+1,m_end);
return item;
}
2.尋找最鄰近的點對
【問題描述】
設(shè)p1=(x1,y1), p2=(x2,y2), … , pn=(xn,yn) 是平面上n個點構(gòu)成的集合S，設(shè)計和實現(xiàn)找出集合S中距離最近點對的算法。
//二維最鄰近點對問題
//#include "stdafx.h"
#include<time.h>
#include<iostream>
#include<cmath>
#include <stdlib.h>
using namespace std;
const int M = 50;
//用類PointX和PointY表示依x坐標和y坐標排好序的點
class PointX {
public:
int operator<=(PointX a)const
{
return (x <= a.x);
}
int ID; //點編號
float x, y; //點坐標
};
class PointY {
public:
int operator<=(PointY a)const
{
return(y <= a.y);
}
int p; //同一點在數(shù)組x中的坐標
float x, y; //點坐標
};
float Random();
template <class Type>
float dis(const Type&u, const Type&v);
bool Cpair2(PointX X[], int n, PointX& a, PointX& b, float& d);
void closest(PointX X[], PointY Y[], PointY Z[], int l, int r, PointX& a, PointX& b, float& d);
template <typename Type>
void Copy(Type a[], Type b[], int left, int right);
template <class Type>
void Merge(Type c[], Type d[], int l, int m, int r);
template <class Type>
void MergeSort(Type a[], Type b[], int left, int right);
int main()
{
srand((unsigned)time(NULL));
int length;
cout << "請輸入點對數(shù)：";
cin >> length;
PointX X[M];
cout << "隨機生成的二維點對為：" << endl;
for (int i = 0; i<length; i++)
{
X[i].ID = i;
X[i].x = Random();
X[i].y = Random();
cout << "(" << X[i].x << "," << X[i].y << ") ";
}
PointX a;
PointX b;
float d;
Cpair2(X, length, a, b, d);
cout << endl;
cout << "最鄰近點對為：(" << a.x << "," << a.y << ")和(" << b.x << "," << b.y << ") " << endl;
cout << "最鄰近距離為： " << d << endl;
return 0;
}
float Random()
{
float result = rand() % 10000;
return result*0.01;
}
//平面上任意兩點u和v之間的距離可計算如下
template <class Type>
inline float dis(const Type& u, const Type& v)
{
float dx = u.x - v.x;
float dy = u.y - v.y;
return sqrt(dx*dx + dy*dy);
}
bool Cpair2(PointX X[], int n, PointX& a, PointX& b, float& d)
{
if (n<2) return false;
PointX* tmpX = new PointX[n];
MergeSort(X, tmpX, 0, n - 1);
PointY* Y = new PointY[n];
for (int i = 0; i<n; i++) //將數(shù)組X中的點復(fù)制到數(shù)組Y中
{
Y[i].p = i;
Y[i].x = X[i].x;
Y[i].y = X[i].y;
}
PointY* tmpY = new PointY[n];
MergeSort(Y, tmpY, 0, n - 1);
PointY* Z = new PointY[n];
closest(X, Y, Z, 0, n - 1, a, b, d);
delete[]Y;
delete[]Z;
delete[]tmpX;
delete[]tmpY;
return true;
}
void closest(PointX X[], PointY Y[], PointY Z[], int l, int r, PointX& a, PointX& b, float& d)
{
if (r - l == 1) //兩點的情形
{
a = X[l];
b = X[r];
d = dis(X[l], X[r]);
return;
}
if (r - l == 2) //3點的情形
{
float d1 = dis(X[l], X[l + 1]);
float d2 = dis(X[l + 1], X[r]);
float d3 = dis(X[l], X[r]);
if (d1 <= d2 && d1 <= d3)
{
a = X[l];
b = X[l + 1];
d = d1;
return;
}
if (d2 <= d3)
{
a = X[l + 1];
b = X[r];
d = d2;
}
else {
a = X[l];
b = X[r];
d = d3;
}
return;
}
//多于3點的情形，用分治法
int m = (l + r) / 2;
int f = l, g = m + 1;
//在算法預(yù)處理階段，將數(shù)組X中的點依x坐標排序，將數(shù)組Y中的點依y坐標排序
//算法分割階段，將子數(shù)組X[l:r]均勻劃分成兩個不想交的子集，取m=(l+r)/2
//X[l:m]和X[m+1:r]就是滿足要求的分割。
for (int i = l; i <= r; i++)
{
if (Y[i].p>m) Z[g++] = Y[i];
else Z[f++] = Y[i];
}
closest(X, Z, Y, l, m, a, b, d);
float dr;
PointX ar, br;
closest(X, Z, Y, m + 1, r, ar, br, dr);
if (dr<d)
{
a = ar;
b = br;
d = dr;
}
Merge(Z, Y, l, m, r);//重構(gòu)數(shù)組Y
//d矩形條內(nèi)的點置于Z中
int k = l;
for ( int i = l; i <= r; i++)
{
if (fabs(X[m].x - Y[i].x)<d)
{
Z[k++] = Y[i];
}
}
//搜索Z[l:k-1]
for (int i = l; i<k; i++)
{
for (int j = i + 1; j<k && Z[j].y - Z[i].y<d; j++)
{
float dp = dis(Z[i], Z[j]);
if (dp<d)
{
d = dp;
a = X[Z[i].p];
b = X[Z[j].p];
}
}
}
}
template <class Type>
void Merge(Type c[], Type d[], int l, int m, int r)
{
int i = l, j = m + 1, k = l;
while ((i <= m) && (j <= r))
{
if (c[i] <= c[j])
{
d[k++] = c[i++];
}
else
{
d[k++] = c[j++];
}
}
if (i>m)
{
for (int q = j; q <= r; q++)
{
d[k++] = c[q];
}
}
else
{
for (int q = i; q <= m; q++)
{
d[k++] = c[q];
}
}
}
template <class Type>
void MergeSort(Type a[], Type b[], int left, int right)
{
if (left<right)
{
int i = (left + right) / 2;
MergeSort(a, b, left, i);
MergeSort(a, b, i + 1, right);
Merge(a, b, left, i, right);//合并到數(shù)組b
Copy(a, b, left, right);//復(fù)制回數(shù)組a
}
}
template <typename Type>
void Copy(Type a[], Type b[], int left, int right)
{
for (int i = left; i <= right; i++)
a[i] = b[i];
}
實驗四
實驗?zāi)康呐c要求：掌握動態(tài)規(guī)劃方法的基本思想與設(shè)計策略。
1.多段圖中的最短路徑問題
【問題描述】
建立一個從源點S到終點T的多段圖，設(shè)計一個動態(tài)規(guī)劃算法求出從S到T的最短路徑值，并輸出相應(yīng)的最短路徑。
#include<iostream>
#include<cmath>
#include<string.h>
#include<stdio.h>
using namespace std;
int dp[100000],alone[100000],a[100000];
int main()
{
int i,j,n,m;
while(~scanf("%d",&m))
{
scanf("%d",&n);
memset(dp,0,sizeof(dp));
memset(alone ,0,sizeof(alone));
for(i=1;i<=n;i++)scanf("%d",&a[i]);
int tmax;
for(i=1;i<=m;i++)//分i段
{
tmax=-(1<<30);
for(j=i;j<=n;j++)
{
dp[j]=max(dp[j-1],alone[j-1])+a[j];
printf("%2d %2d %2d\n",a[j],alone[j-1],dp[j]);
if(j>i)alone[j-1]=tmax;
if(tmax<dp[j])tmax=dp[j];
}
}
printf("%d\n",tmax);
}
return 0;
}
2.有向無環(huán)圖中的最短路徑問題
【問題描述】
建立一個從源點S到終點E的有向無環(huán)圖，設(shè)計一個動態(tài)規(guī)劃算法求出從S到E的最短路徑值，并輸出相應(yīng)的最短路徑。
/*Dijkstra求單源最短路徑 2010.8.26*/
#include <iostream>
#include <stack>
#include <stdlib.h>
#define M 100
#define N 100
using namespace std;
typedef struct node
{
int matrix[N][M]; //鄰接矩陣
int n; //頂點數(shù)
int e; //邊數(shù)
}MGraph;
void DijkstraPath(MGraph g,int *dist,int *path,int v0) //v0表示源頂點
{
int i,j,k;
bool *visited=(bool *)malloc(sizeof(bool)*g.n);
for(i=0;i<g.n;i++) //初始化
{
if(g.matrix[v0][i]>0&&i!=v0)
{
dist[i]=g.matrix[v0][i];
path[i]=v0; //path記錄最短路徑上從v0到i的前一個頂點
}
else
{
dist[i]=INT_MAX; //若i不與v0直接相鄰，則權(quán)值置為無窮大
path[i]=-1;
}
visited[i]=false;
path[v0]=v0;
dist[v0]=0;
}
visited[v0]=true;
for(i=1;i<g.n;i++) //循環(huán)擴展n-1次
{
int min=INT_MAX;
int u;
for(j=0;j<g.n;j++) //尋找未被擴展的權(quán)值最小的頂點
{
if(visited[j]==false&&dist[j]<min)
{
min=dist[j];
u=j;
}
}
visited[u]=true;
for(k=0;k<g.n;k++) //更新dist數(shù)組的值和路徑的值
{
if(visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k]<dist[k])
{
dist[k]=min+g.matrix[u][k];
path[k]=u;
}
}
}
}
void showPath(int *path,int v,int v0) //打印最短路徑上的各個頂點
{
stack<int> s;
int u=v;
while(v!=v0)
{
s.push(v);
v=path[v];
}
s.push(v);
while(!s.empty())
{
cout<<s.top()<<" ";
s.pop();
}
}
int main(int argc, char *argv[])
{
int n,e; //表示輸入的頂點數(shù)和邊數(shù)
cout<<"輸入的頂點數(shù)和邊數(shù):";
while(cin>>n>>e&&e!=0)
{
int i,j;
int s,t,w; //表示存在一條邊s->t,權(quán)值為w
MGraph g;
int v0;
int *dist=(int *)malloc(sizeof(int)*n);
int *path=(int *)malloc(sizeof(int)*n);
for(i=0;i<N;i++)
for(j=0;j<M;j++)
g.matrix[i][j]=0;
g.n=n;
g.e=e;
cout<<"輸入起始點，終點，權(quán)值"<<endl;
for(i=0;i<e;i++)
{
cin>>s>>t>>w;
g.matrix[s][t]=w;
}
cout<<"輸入源頂點";
cin>>v0; //輸入源頂點
DijkstraPath(g,dist,path,v0);
for(i=0;i<n;i++)
{
if(i!=v0)
{
showPath(path,i,v0);
cout<<"dist"<<":"<<dist[i]<<endl;
}
}
}
return 0;
}
3.最長遞增子序列問題
【問題描述】
給定一個整數(shù)數(shù)組，設(shè)計一個動態(tài)規(guī)劃算法求出該數(shù)組中的最長遞增子序列。
#include <iostream>
using namespace std;
// 輸出LIS 序列
void outputLIS(int * arr, int index, int lis, int *L)
{
//終止條件
if (lis == 0 || index < 0)
return;
//找到第一個L[index]==lis
while (L[index]!=lis && index>0)
index--;
//反序輸出
if (index >= 0 && L[index]==lis)
{
outputLIS(arr, index - 1, lis - 1, L);
cout << arr[index] << " ";
}
}
int LIS(int *a, int n)
{
//定義一個存取結(jié)果的數(shù)組
int *L = new int[n];
//填寫次序 0 to n-1
for (int j = 0; j < n;j++)
{
L[j] = 1;//BaseCase
//find max L[i]
for (int i = 0; i < j;i++)
{
if (a[i]<a[j] && L[i]+1 > L[j])
{
L[j] = L[i] + 1;
}
}
}
//return the max of L[0~n-1]
int max = L[0];
for (int i = 0; i < n; i++)
{
//cout << L[i] << " ";
if (L[i]>max)
{
max = L[i];
}
}
//回溯輸出
cout << "最長遞增子序列如下：";
outputLIS(a, n,max, L);
return max;
}
int main()
{
int a[] = { 5, 2, 3, 2 ,8, 6, 2, 4, 5, 7};
for(int i=0;i<10;i++)
cout<<a[i]<<" ";
cout<<endl;
int n = sizeof(a) / sizeof(int);
cout<<endl<<"長度為：" << LIS(a, n) << endl;
return 0;
}
4.矩陣連乘問題
【問題描述】
給定n個矩陣{A1，A2，…,An},其中AiAi+1是可乘的，i=1，2，…，n-1,考察這n個矩陣的連乘積A1A2…An，設(shè)計一個動態(tài)規(guī)劃算法，求出這個矩陣連乘積問題的最優(yōu)計算順序。
實現(xiàn)要求：隨機生成n個合法的可連乘的矩陣，以完全加括號的方式輸出其最優(yōu)計算順序。
#include <iostream>
using namespace std;
const int L = 7;
int RecurMatrixChain(int i,int j,int **s,int *p);//遞歸求最優(yōu)解
void Traceback(int i,int j,int **s);//構(gòu)造最優(yōu)解
int main()
{
int p[L]={30,35,15,5,10,20,25};
int **s = new int *[L];
for(int i=0;i<L;i++)
{
s[i] = new int[L];
}
cout<<"矩陣的最少計算次數(shù)為："<<RecurMatrixChain(1,6,s,p)<<endl;
cout<<"矩陣最優(yōu)計算次序為："<<endl;
Traceback(1,6,s);
return 0;
}
int RecurMatrixChain(int i,int j,int **s,int *p)
{
if(i==j) return 0;
int u = RecurMatrixChain(i,i,s,p)+RecurMatrixChain(i+1,j,s,p)+p[i-1]*p[i]*p[j];
s[i][j] = i;
for(int k=i+1; k<j; k++)
{
int t = RecurMatrixChain(i,k,s,p) + RecurMatrixChain(k+1,j,s,p) + p[i-1]*p[k]*p[j];
if(t<u)
{
u=t;
s[i][j]=k;
}
}
return u;
}
void Traceback(int i,int j,int **s)
{
if(i==j) return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"("<<i<<","<<s[i][j]<<")";
cout<<"*("<<(s[i][j]+1)<<","<<j<<")"<<endl;
}
實驗五
實驗?zāi)康呐c要求：掌握動態(tài)規(guī)劃方法的基本思想與設(shè)計策略。
1.最長公共子序列問題
【問題描述】
⑴ 給定兩個字符串X和Y，設(shè)計一個動態(tài)規(guī)劃算法，求出這兩個字符串的最長公共子序列，并輸出該子序列。
⑵ 若僅要求求出兩個字符串的最長公共子序列的長度值，為節(jié)省存儲空間，采用“滾動數(shù)組”方式實現(xiàn)動態(tài)規(guī)劃算法。
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
bool isodd(int i)
{
if(i%2==0)
return false;
else
return true;
}
int main()
{
vector<char> a={'a','c','b','b','a'};
vector<char> b={'a','c','d','b','c','d','b'};
int bsize=b.size();
int dp[2][bsize];
memset(dp,0,sizeof(dp));
for(int i=0;i<a.size();i++)
for(int j=0;j<b.size();j++)
if(!isodd(i))//i是偶數(shù)
{
if(a[i]==b[j])
if(i==0||j==0) dp[1][j]=1;
else dp[1][j]=dp[0][j-1]+1;
else
if(i==0||j==0) dp[1][j]=dp[0][j];
else dp[1][j]=max(dp[0][j],dp[1][j-1]);
}
else
{
if(a[i]==b[j])
if(i==0||j==0) dp[0][j]=1;
else dp[0][j]=dp[1][j-1]+1;
else
if(i==0||j==0) dp[0][j]=dp[1][j];
else dp[0][j]=max(dp[1][j],dp[0][j-1]);
}
cout<<"最長公共子序列:";
if(isodd(a.size()))
cout<<dp[1][b.size()-1];
else
cout<<dp[0][b.size()-1];
return 0;
}
2.0-1背包問題
【問題描述】
給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為W（假定物品重量與背包容量值均為整數(shù)），應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大？設(shè)計一個動態(tài)規(guī)劃算法，求解背包問題。
K(w,j)=max{k(w-wj,j-1)+vj,k(w,j-1)}
#include <iostream>
#include <cstring>
using namespace std;
#define W 50
void Trackback(int *weight, int n, int w,bool *p,int **a)
{
if (n==0 || w==0)
return;
if (a[w][n]==a[w][n-1])//若和左邊的一致，說明沒有選最后一個
{
p[n - 1] = false;
Trackback(weight, n - 1, w, p, a);
}
else
{
p[n - 1] = true;
Trackback(weight, n - 1, w-weight[n-1], p, a);
}
}
int getMaxValue(int w, int n, int *price, int * weight )
{
//創(chuàng)建一個 w+1 * n+1 的二維表
int **a = new int *[w + 1];
for (int i = 0; i < w + 1;i++)
{
a[i] = new int[n + 1];
}
//創(chuàng)建一個數(shù)組 記錄貨物是否取的狀態(tài)
bool *p = new bool[w];
memset(p, false, sizeof(p));
//base case
for (int i = 0; i < w + 1; i++)
a[i][0] = 0;
for (int i = 0; i < n + 1; i++)
a[0][i] = 0;
//for
for (int i = 1; i < w + 1;i++)
{
for (int j = 1; j < n + 1;j++)
{
if (i<weight[j-1])//填寫a[i][j]，若當(dāng)前背包重量小于物品，則不裝
{
a[i][j] = a[i][j - 1];
}
else
{
if (a[i][j-1] <= a[i-weight[j-1]][j-1] + price[j-1])
{
a[i][j] = a[i - weight[j - 1]][j - 1] + price[j - 1] ;
}
else
a[i][j] = a[i][j - 1];
}
}
}
Trackback(weight, n, w, p, a);
cout << "從左到右是否取件為：";
for (int i = 0; i < n; i++)
cout << p[i] << " ";
cout << endl;
return a[w][n];
}
int main()
{
int price[] = { 300, 100, 30 ,200};
int weight[] = { 10, 20, 30 ,5};
cout << "背包問題的解是："<<getMaxValue(W, 4, price, weight) << endl;
return 0;
}
實驗六
實驗?zāi)康呐c要求：
（1） 掌握樹型動態(tài)規(guī)劃方法的基本思想與設(shè)計策略；
（2） 掌握貪心法的基本思想和設(shè)計方法。
1.樹中的最大獨立集問題
【問題描述】
給定一個無回路的無向圖（即樹），設(shè)計一個動態(tài)規(guī)劃算法，求出該圖的最大獨立集，并輸出該集合中的各個頂點值。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN=100;
vector<int> G[MAXN]; //G[i]表示頂點i的鄰接點
int l[MAXN]; //結(jié)點層次
int p[MAXN]; //根樹
int dp[MAXN]; //dp數(shù)組
int sumC[MAXN]; //孩子DP和
int sumS[MAXN]; //孫子DP和
int maxL; //最大層次
int n;
void readTree()
{
int u,v;
cin>>n;
for(int i=0;i<n-1;++i)
{
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
}
void dfs(int u,int fa)
{
int d=G[u].size();
l[u]= (fa==-1)? 0: (l[fa]+1);
if(l[u]>maxL)
{
maxL=l[u];
}
for(int i=0;i<d;++i)
{
int v=G[u][i];
if(v!=fa)
{
dfs(v,p[v]=u);
}
}
}
int rootDp(int u)
{
//構(gòu)造u根樹
p[u]=-1;
maxL=-1;
dfs(u,p[u]);
for(int i=maxL;i>=0;--i)
{
for(int j=0;j<n;++j)
{
if(l[j]==i)
{
if (sumS[j]+1>sumC[j])
{
dp[j]=sumS[j]+1;
}
else
dp[j] = sumC[j];
if(i-1>=0)
{
sumC[p[j]]+=dp[j];
}
if(i-2>=0)
{
sumS[p[p[j]]]+=dp[j];
}
}
}
}
return dp[u];
}
int main()
{
readTree();
int res=-1;
//分別以每個頂點為根
for(int i=0;i<n;++i)
{
memset(sumS,0,sizeof(sumS));
memset(sumC,0,sizeof(sumC));
int tmp;
if((tmp=rootDp(i))>res)
res=tmp;
}
cout<<res<<endl;
return 0;
}
2.區(qū)間調(diào)度問題
【問題描述】
給定n個活動，其中的每個活動ai包含一個起始時間si與結(jié)束時間fi。設(shè)計與實現(xiàn)算法從n個活動中找出一個最大的相互兼容的活動子集S。
要求：分別設(shè)計動態(tài)規(guī)劃與貪心算法求解該問題。其中，對貪心算法分別給出遞歸與迭代兩個版本的實現(xiàn)。
貪心算法
#include <iostream>
using namespace std;
//i是上一個符合條件的id，為了完整性，在第一列加上-1，n是總數(shù)目
void GetSet(int *si, int *fi, int i, int n)
{
int m = i + 1;
while (m <= n && si[m] < fi[i])//找第一個符合的
m = m + 1;
if (m <= n)
{
cout <<m<<" ";
GetSet(si, fi, m, n);
}
}
int main()
{
int si[] = { -1,1, 3, 0, 5, 3, 5, 6, 8, 8, 2};
int fi[] = { -1,4, 5, 6, 7, 8, 9, 10, 11, 12, 13 };
int n = 11;
cout<<"兼容的活動為：";
GetSet(si, fi, 0, 10);
}
#include<iostream>
using namespace std;
//動態(tài)規(guī)劃實現(xiàn)
int GetSet(int *start, int *finish, int n)
{
//c[i][j]表示第i個工作結(jié)束后到第j個工作開始前之間存在的可兼容的工作個數(shù)
//new c[i][j]
int **c = new int *[n];
for(int i=0; i<n; i++)
c[i] = new int[n];
//c[i][j]初始賦值
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
c[i][j] = 0;
for(int j=0; j<n; j++)
{
for(int i=0; i<n; i++)
{
if(i<j)
{
int s = finish[i];
int f = start[j];
for(int k=i+1; k<j; k++)
if(start[k]>=s && finish[k]<=f)
{
if(c[i][j]<(c[i][k]+c[k][j]+1))
c[i][j] = c[i][k]+c[k][j]+1; //分解成更小子問題
}
}
}
}
return c[0][n-1]; //最終目標
}
int main()
{
//已經(jīng)按完成時間排好序
int start[] = {-1,3,0,5,3,5,6,8,8,2,1000};
int finish[] = {0,5,6,7,8,10,10,11,12,13,10000};
int n = 11; //活動只有9個
cout<<"最大兼容活動子集的大小為："<<GetSet(start, finish, n)<<endl;
return 0;
}
實驗七
實驗?zāi)康呐c要求：
（1） 掌握貪心法的基本思想和設(shè)計方法。
1.區(qū)間劃分問題
【問題描述】
給定一組報告，其中的每個報告設(shè)置了一個開始時間si和結(jié)束時間fi。設(shè)計與實現(xiàn)一個算法，對這組報告分配最少數(shù)量的教室，使得這些報告能無沖突的舉行。
#include <iostream>
#include <stdlib.h>
using namespace std;
#define N 100
struct Report
{
int num;//報告編號
int begin;//開始時間
int end;//結(jié)束時間
bool flag;//是否已分配教室
int classroom;//教室號
};
void QuickSort(Report* rep,int f,int t)//一開始將所有報告按結(jié)束時間排序
{
if(f<t)
{
int i=f-1,j=f;
Report r=rep[t];
while(j<t)
{
if(rep[j].end<=r.end)
{
i++;
Report tmp=rep[i];
rep[i]=rep[j];
rep[j]=tmp;
}
j++;
}
Report tmp1=rep[t];
rep[t]=rep[i+1];
rep[i+1]=tmp1;
QuickSort(rep,f,i);
QuickSort(rep,i+2,t);
}
}
int select_room(Report *rep,int *time,int n)
{
//第一個報告分給第一個教室
int i=1,j=1;//i報告，j教室
int sumRoom=1;
int sumRep=1;//教室已分配的報告數(shù)
time[1]=rep[0].end;
rep[0].classroom=1;
for(i=1;i<n;i++)
{
for(j=1;j<=sumRoom;j++)
{
if((rep[i].begin>=time[j])&&(!rep[i].flag))
{
rep[i].classroom=j;
rep[i].flag=true;
time[j]=rep[i].end;
sumRep++;
}
}
if(sumRep<n&&i==n-1)//報告沒有分配完
{
i=0;
sumRoom++;
}
}
return sumRoom;
}
int main()
{
int n;
Report rep[N];
int time[N];//每個教室最后一個報告的結(jié)束時間
cout<<"請輸入報告數(shù)量:"<<endl;
cin>>n;
int i;
for(i=0;i<n;i++)
{
//初始化
time[i+1]=0;//time[1]~time[10]
rep[i].num=i+1;//編號1~10
rep[i].flag=false;
rep[i].classroom=0;
cout<<"報告"<<i+1<<"開始時間:";
cin>>rep[i].begin;
cout<<"報告"<<i+1<<"結(jié)束時間:";
cin>>rep[i].end;
}
QuickSort(rep,0,n-1);
int roomNum=select_room(rep,time,n);
cout<<"所用教室總數(shù)為:"<<roomNum<<endl;
for(i=0;i<n;i++)
{
cout<<"活動"<<rep[i].num<<"在教室"<<rep[i].classroom<<"中"<<endl;
}
system("pause");
return 0;
}
2.最小延遲調(diào)度問題
【問題描述】
假定有一單個的資源在一個時刻只能處理一個任務(wù)?，F(xiàn)給定一組任務(wù)，其中的每個任務(wù)i包含一個持續(xù)時間ti和截止時間di。設(shè)計與實現(xiàn)一個算法，對這組任務(wù)給出一個最優(yōu)調(diào)度方案，使其對所有任務(wù)的最大延遲最小化。
#include<iostream>
using namespace std;
#define N 100
struct Mission
{
int num;
int last;
int end;
};
void QuickSort(Mission *mi,int f,int t)
{
if(f<t)
{
int i=f-1,j=f;
Mission m=mi[t];
while(j<t)
{
if(mi[j].end<=m.end)
{
i++;
Mission tmp=mi[i];
mi[i]=mi[j];
mi[j]=tmp;
}
j++;
}
Mission tmp1=mi[t];
mi[t]=mi[i+1];
mi[i+1]=tmp1;
QuickSort(mi,f,i);
QuickSort(mi,i+2,t);
}
}
int main()
{
int n;
cout<<"請輸入任務(wù)總數(shù):"<<endl;
cin>>n;
Mission mi[N];//Mission[0]~Mission[n-1]
int start[N+1];//排好序的任務(wù)的開始時間，start[1]~start[n]
for(int i=0;i<n;i++)
{
mi[i].num=i+1;
cout<<"任務(wù)"<<i+1<<"的持續(xù)時間為:";
cin>>mi[i].last;
cout<<"任務(wù)"<<i+1<<"的截止時間為:";
cin>>mi[i].end;
}
QuickSort(mi,0,n-1);
int delay=0;
start[1]=0;
if(start[1]+mi[0].last>mi[0].end)
{
delay+=start[1]+mi[0].last-mi[0].end;//如果開始時間+持續(xù)時間>截止時間，累計延遲
}
for(int i=1;i<n;i++)
{
start[i+1]=start[i]+mi[i-1].last;
if(start[i+1]+mi[i].last>mi[i].end)
{
delay+=start[i+1]+mi[i].last-mi[i].end;
}
}
cout<<"延遲最小為:"<<delay<<endl;
for(int i=0;i<n;i++)
{
cout<<"任務(wù)"<<mi[i].num<<"的執(zhí)行時間:["<<start[i+1]<<","<<mi[i].last+start[i+1]<<"]"<<endl;
}
}
實驗八
實驗?zāi)康呐c要求：
（2） 掌握使用圖的深度優(yōu)先搜索算法實現(xiàn)對有向圖中是否包含環(huán)的判斷；
（3） 掌握使用圖的深度優(yōu)先搜索算法實現(xiàn)對有向圖的強連通分量的劃分。
1.有向圖中環(huán)的判斷問題
【問題描述】
給定一個有向圖，要求使用深度優(yōu)先搜索策略，判斷圖中是否存在環(huán)。
#include<iostream>
#include<malloc.h>
using namespace std;
#define maxNum 100 //定義鄰接舉證的最大定點數(shù)
int pre[maxNum];
int post[maxNum];
int point=0;//pre和post的值
bool is_DAG=true;//標識位，表示有向無環(huán)圖
/*
0 白色，未被訪問過的節(jié)點標白色
-1 灰色，已經(jīng)被訪問過一次的節(jié)點標灰色
1 黑色，當(dāng)該節(jié)點的所有后代都被訪問過標黑色
時間復(fù)雜度：O(n+e)
*/
int color[maxNum];//頂點顏色表 color[u]
//圖的鄰接矩陣表示結(jié)構(gòu)
typedef struct
{
char v[maxNum];//圖的頂點信息
int e[maxNum][maxNum];//圖的頂點信息
int vNum;//頂點個數(shù)
int eNum;//邊的個數(shù)
}graph;
void createGraph(graph *g);//創(chuàng)建圖g
void DFS(graph *g);//深度優(yōu)先遍歷圖g
void dfs(graph *g,int i);//從頂點i開始深度優(yōu)先遍歷與其相鄰的點
void dfs(graph *g,int i)
{
//cout<<"頂點"<<g->v[i]<<"已經(jīng)被訪問"<<endl;
cout<<"頂點"<<i<<"已經(jīng)被訪問"<<endl;
color[i]=-1;
pre[i]=++point;
for(int j=1;j<=g->vNum;j++)
{
if(g->e[i][j]!=0)
{
if(color[j]==-1)//探索到回邊,存在環(huán)
{
is_DAG=false;//不是有向無環(huán)圖
}
else if(color[j]==0)
dfs(g,j);
}
}
post[i]=++point;
color[i]=1;//表示i的后裔節(jié)點都被訪問過
}
void DFS(graph *g)
{
int i;
//初始化color數(shù)組，表示一開始所有頂點都未被訪問過，//初始化pre和post
for(i=1;i<=g->vNum;i++)
{
color[i]=0;
pre[i]=0;
post[i]=0;
}
//深度優(yōu)先搜索
for(i=1;i<=g->vNum;i++)
{
if(color[i]==0)//如果這個頂點為被訪問過，則從i頂點出發(fā)進行深度優(yōu)先遍歷
{
dfs(g,i);
}
}
}
void createGraph(graph *g)//創(chuàng)建圖g
{
cout<<"請輸入頂點個數(shù):";
cin>>g->vNum;
cout<<"請輸入邊的個數(shù):";
cin>>g->eNum;
int i,j;
//初始畫圖g
for(i=1;i<=g->vNum;i++)
for(j=1;j<=g->vNum;j++)
g->e[i][j]=0;
//輸入邊的情況
cout<<"請輸入邊的頭和尾"<<endl;
for(int k=1;k<=g->eNum;k++)
{
cin>>i>>j;
g->e[i][j]=1;
}
}
int main()
{
graph *g;
g=(graph*)malloc(sizeof(graph));
createGraph(g);//創(chuàng)建圖g
DFS(g);//深度優(yōu)先遍歷
//各頂點的pre和post值
// for(int i=1;i<=g->vNum;i++)
// cout<<"頂點"<<i<<"的pre和post分別為："<<pre[i]<<" "<<post[i]<<endl;
//判斷是否是有向無環(huán)圖
if(is_DAG)
cout<<"有向無環(huán)圖"<<endl;
else
cout<<"存在環(huán)"<<endl;
int k;
cin>>k;
return 0;
}
2.有向圖的強連通分量問題
【問題描述】
給定一個有向圖，設(shè)計一個算法，求解并輸出該圖的各個強連通分量。
#include <iostream>
#include <stack>
using namespace std;
#define MAX_VERTEX_SIZE 10001
struct EdgeNode{
int vertex;
EdgeNode *nextArc;
};
struct VerTexNode{
EdgeNode* firstArc;
};
struct Graph{
int n,e;
VerTexNode vNode[MAX_VERTEX_SIZE];
};
int time = 0;
int low[MAX_VERTEX_SIZE];
int dfn[MAX_VERTEX_SIZE];
int visited[MAX_VERTEX_SIZE];
int inStack[MAX_VERTEX_SIZE];
stack<int> st;
Graph graph;
void initeGraph(int n,int m)
{
for(int i = 1;i<=n;i++)
{
graph.vNode[i].firstArc = NULL;
}
graph.n = n;
graph.e = m;
}
//頭插法建立圖
void creatGraph(int s,int v)
{
EdgeNode *edgeNode = new EdgeNode;
edgeNode->vertex = v;
edgeNode->nextArc = graph.vNode[s].firstArc;
graph.vNode[s].firstArc = edgeNode;
}
int min(int a,int b)
{
if(a>b)
return b;
else
return a;
}
void trajan(int u)
{
dfn[u] = low[u] = time++;
st.push(u);
visited[u] = 1;
inStack[u] = 1;
EdgeNode *edgePtr = graph.vNode[u].firstArc;
while(edgePtr !=NULL)
{
int v = edgePtr->vertex;
if(visited[v] == 0)
{
trajan(v);
low[u] = min(low[u],low[v]);
}
else
{
low[u] = min(low[u],dfn[v]);
}
edgePtr = edgePtr->nextArc;
}
if(dfn[u] == low[u])
{
int vtx;
cout<<"set is: ";
do{
vtx = st.top();
st.pop();
inStack[vtx] = 0;//表示已經(jīng)出棧
cout<<vtx<<' ';
}while(vtx !=u );
}
}
int main()
{
int n,m;
int s,a;
cout<<"vexs and edges:"<<endl;
cin>>n>>m;
initeGraph(n,m);
for(int i = 1;i<=n;i++)
{
visited[i] = 0;
inStack[i] = 0;
dfn[i] = 0;
low[i] = 0;
}
cout<<"the begin and the end of each edge:"<<endl;
for(int j = 1;j<=m;j++)
{
cin>>s>>a;
creatGraph(s,a);
}
for(int i =1;i<=n;i++)
if(visited[i] == 0)
trajan(i);
return 0;
}
實驗九
實驗?zāi)康呐c要求：
（4） 理解與掌握求解最大流與最小割的基本算法。
（5） 學(xué)會應(yīng)用最大流與最小割算法解決實際問題。
1.實現(xiàn)Ford-Fulkerson算法，求出給定圖中從源點s到匯點t的最大流，并輸出最小割。
#include<queue>
#include<iostream>
#include<string.h>
using namespace std;
#define MAX 1024
int nodes,edges;
int capacity[MAX][MAX];//記錄邊的當(dāng)前還可以通過的最大流量
int maxflow=0;
bool isVisited[MAX];//在BFS或DFS找增廣路的時候記錄該元素是否訪問過
int pre[MAX];//記錄節(jié)點的前一個節(jié)點
/*
我最疑惑的地方是capacity[i][pre[i]]+=increase;這個地方。
我們一開始以為這只是一個簡單的有向圖，其實不是，這個有向圖會根據(jù)它的兩個節(jié)點之間的通過的流量自動改變
我們可以把它看成是最原始的有向圖中有箭頭的兩個節(jié)點可以相互通過流，而不僅僅是沿箭頭的方向通過流（通過判斷兩個節(jié)點之間的最大
流量來判斷。）
表達能力實在有限。。我自己都覺得沒說清楚..
*/
inline int min(int a,int b)
{
return a>b?b:a;
}
bool DFS(int src)
{
if(!src)
pre[src]=-1;
if(src==nodes-1)
return true;
isVisited[src]=true;
for(int i=0;i<nodes;i++)
{
if(!isVisited[i]&&capacity[src][i])
{
isVisited[i]=true;
pre[i]=src;
if(DFS(i))
return true;
}
}
return false;
}
bool BFS()
{
queue<int> myQueue;
myQueue.push(0);
isVisited[0]=true;
pre[0]=-1;
while(!myQueue.empty())
{
int current=myQueue.front();
myQueue.pop();
for(int i=0;i<nodes;i++)
{
if(!isVisited[i]&&capacity[current][i])
{
myQueue.push(i);
pre[i]=current;
isVisited[i]=true;
}
}
}
return isVisited[nodes-1];
}
void MaxFlow()
{
while(1)
{
memset(isVisited,false,nodes);
memset(pre,0xff,4*nodes);
// if(!DFS(0))
// break;
if(!BFS())
break;
int increase=MAX;
int i;
for(i=nodes-1;pre[i]>=0;i=pre[i])
{
increase=min(increase,capacity[pre[i]][i]);
}
for(i=nodes-1;pre[i]>=0;i=pre[i])
{
capacity[pre[i]][i]-=increase;
capacity[i][pre[i]]+=increase;
}
maxflow+=increase;
}
}
int main()
{
while(1)
{
cout<<"vexs edges:"<<endl;
cin>>nodes>>edges;
int firstnode,secondenode,capa;
for(int i=0;i<edges;i++)
{
cin>>firstnode>>secondenode>>capa;
capacity[firstnode][secondenode]=capa;
}
MaxFlow();
cout<<"最大流："<<maxflow<<endl;
maxflow=0;
}
return 0;
}
2.設(shè)計與實現(xiàn)二部圖匹配（Bipartite Matching）問題的算法。
//void *memset(void *s,int c,size_t n)將已開辟內(nèi)存空間 s 的首 n 個字節(jié)的值設(shè)為值 c
//#include <Ford_Fulkerson>
#include <algorithm>
#include <cstdio>
#include <list>
#include <queue>
#include <iostream>
using namespace std;
#define INFI 1000
typedef struct _mark
{
int pre_suc;
int max_incr;
}MARK;
int iteration = 0;//增光路徑數(shù)目
const int N = 100;
list<int> setS;
bool isMark[N], isCheck[N], isDone;
MARK markList[N];
int c[N][N], f[N][N];
int n; //頂點數(shù)
int Maxflow()
{
int flow = 0;
for (int i = 0; i<n; i++)
{
flow += f[0][i];
}
return flow;
}
void Mincut()//isMark的點就是最小割
{
int i = 0;
while (i<n)
{
if (isMark[i])
setS.push_back(i);
i++;
}
}
int IncrFlowAuxi(int index)//計算增廣路徑中的最大可增量
{
if (index == 0)
return markList[index].max_incr;
int prev = markList[index].pre_suc;
int maxIncr = markList[index].max_incr;
return min(maxIncr, IncrFlowAuxi(prev));//遞歸求瓶頸值為最大增量
}
void IncrFlow()//增廣路徑的增加
{
iteration++;
int incr = IncrFlowAuxi(n - 1); //最大可增量
int index = n - 1;
int prev;
while (index != 0)
{
if (index != n - 1)
cout << index << " ";
prev = markList[index].pre_suc;
f[prev][index] += incr; //增廣路徑增加后，相應(yīng)的流量進行更新
index = prev;
}
cout << endl;
}
void Mark(int index, int pre_suc, int max_incr)//被標記表示可能被納入新路徑
{
isMark[index] = true;
markList[index].pre_suc = pre_suc;//前驅(qū)
markList[index].max_incr = max_incr;//當(dāng)前路徑的流值
}
void Check(int i)//被mark且被check的點表示已經(jīng)被納入新路徑
{
isCheck[i] = true;
for (int j = 0; j<n; j++)
{
if (c[i][j]>0 && !isMark[j] && c[i][j]>f[i][j])//forward 邊
Mark(j, i, min(markList[i].max_incr, c[i][j] - f[i][j]));
if (c[j][i]>0 && !isMark[j] && f[j][i]>0)//reverse 邊
Mark(j, i, min(markList[i].max_incr, f[j][i]));
}
}
//ford_fulkerson算法
int ford_fulkerson()
{
int i;
while (1)//一次循環(huán)找到一個新路徑
{
isDone = true;
i = 0;
while (i<n)//一次循環(huán)判斷上次循環(huán)是否有找到新路徑，若無則表明沒有新路徑，終止算法
{
if (isMark[i] && !isCheck[i]) //判斷是否所有標記的點都已被檢查：若是，結(jié)束整個算法
{
isDone = false;
break;
}
i++;
}
if (isDone) //算法結(jié)束，則計算最小割和最大流
{
Mincut();
return Maxflow();
}
while (i<n)//貪心法構(gòu)建新路徑
{
if (isMark[i] && !isCheck[i]) {
Check(i);
i = 0;
}
if (isMark[n - 1]) //如果匯t被標記，說明找到了一條增廣路徑，則增加該條路徑的最大可增加量
{
IncrFlow();
memset(isMark + 1, false, n - 1); //增加該增廣路徑后，除了源s，其余標記抹去
memset(isCheck, false, n);
}
else i++;
}
}
}
int main()
{
//測試數(shù)據(jù)為ppt第40頁的圖，只實現(xiàn)了二部圖的最大匹配
n = 12;
for (int k = 0; k < n; ++k)
{
memset(c[k], 0, sizeof(c[0][0])*n);
memset(f[k], 0, sizeof(f[0][0])*n); //初始各分支流量為0
memset(isMark, false, n);
memset(isCheck, false, n);
}
isMark[0] = true; //給源做永久標記
markList[0].max_incr = INFI;
markList[0].pre_suc = INFI;
c[1][6] = INFI;
c[1][7] = INFI;
c[2][7] = INFI;
c[3][6] = INFI;
c[3][8] = INFI;
c[3][9] = INFI;
c[4][7] = INFI;
c[4][10] = INFI;
c[5][7] = INFI;
c[5][10] = INFI;
for (int i = 1; i < n / 2; i++)
c[0][i] = 1;
for (int i = n/2; i < n-1; i++)
c[i][n-1] = 1;
cout << "最大匹配結(jié)果為：" << endl;
int result= ford_fulkerson();
cout << "匹配邊個數(shù)為：" << result << endl;
system("PAUSE");
}
3.設(shè)計與實現(xiàn)項目選擇（Project Selection）問題的算法。
