2011年全国数学建模B题附录程序

Categories: 一点兴趣
Comments: 7 Comments
Published on: 2011 年 09 月 12 日

附录程序
附录一:
function graph=floyd(graph)
v=size(graph,1);
for k=1:v
for i=1:v
for j=1:v
if((graph(i,j)==-1 || graph(i,j) > graph(i,k) + graph(k,j)) && graph(i,k)~= -1 && graph(k,j)~=-1 )
graph(i,j) = graph(i,k) + graph(k,j);
end
end
end
end

附录二:
%
[map,data]=buildmap();
graph=floyd(map);
edges=data;
e=edges;
g=graph;
police(1:92)=0;
police(1:20)=1;
father=find_father(graph,police)
f=father;
rune()

ep=getpoints(father,graph,edges)

n=size(e,1);hold on;
cor=['r','m','b','c','k','m','y','r','g','b','c','k','m','y','r','r','b','c','k','m','y','r','g','b','c','k','m','y']
for i=1:n
if(ep(i,1)==0&&ep(i,2)==0)
plot([e(i,3),e(i,5)],[e(i,4),e(i,6)],cor(father(e(i,1))));
else
plot([e(i,3),ep(i,1)],[e(i,4),ep(i,2)],[cor(father(e(i,1))),'-']);
plot([e(i,5),ep(i,1)],[e(i,6),ep(i,2)],[cor(father(e(i,2))),'-']);
plot(ep(i,1),ep(i,2),'.');
end
end
for i=1:n
if(e(i,1)<=20) plot(e(i,3),e(i,4),'o');end if(e(i,2)<=20) plot(e(i,5),e(i,6),'o');end; if(e(i,1)>20&&e(i,2)>20) plot(e(i,3),e(i,4),'r.');plot(e(i,5),e(i,6),'r.');
end
text(e(i,3),e(i,4),num2str(e(i,1)));
end
text(444,360,'92');

function arr=getpoints(father,graph,edges)
n=size(edges(:,1),1);
arr=zeros(n,2);
for i=1:n
if(father(edges(i,1))~=father(edges(i,2)))
dis=sqrt((edges(i,3)-edges(i,5))^2+(edges(i,4)-edges(i,6))^2)
l=(graph(father(edges(i,2)),edges(i,2))-graph(father(edges(i,1)),edges(i,1))+dis)/2
arr(i,1)=edges(i,3)+(edges(i,5)-edges(i,3))*l/dis;
arr(i,2)=edges(i,4)+(edges(i,6)-edges(i,4))*l/dis;
end
end
end

附录三
求father。

附录四
本lingo程序用来求二分图最大权边最小
sets:
jingting/1..20/;
chukou/1..13/:cu,y;
num92/1..92/;
link(chukou,jingting):x;
matrix(num92,num92):c;

endsets
data:
cu=12 14 16 21 22 23 24 28 29 30 38 48 62;
c=@file('C:\Users\iphxer\Documents\MATLAB\g.txt');
enddata

@for(link:@bin(x));
@for(chukou(i):@sum(jingting(j):x(i,j))=1);
@for(jingting(j):@sum(chukou(i):x(i,j))<=1); @for(chukou(i):y(i)=@sum(jingting(j):x(i,j)*c(cu(i),j))); fx=@max(chukou(i):y(i)); min=fx; 附录五 本lingo程序是求最优完全二分图匹配 sets: jingting/1..20/; chukou/1..13/:cu,y; num92/1..92/; link(chukou,jingting):x; matrix(num92,num92):c; endsets data: cu=12 14 16 21 22 23 24 28 29 30 38 48 62; c=@file('C:\Users\iphxer\Documents\MATLAB\g.txt'); enddata @for(link:@bin(x)); @for(chukou(i):@sum(jingting(j):x(i,j))=1); @for(jingting(j):@sum(chukou(i):x(i,j))<=1); @for(chukou(i):@max(jingting(j):x(i,j)*c(cu(i),j))<80.1546); min=@sum(link(i,j):x(i,j)*C(cu(i),j)); 附录六 function fun(f,morelen) %FUN Summary of this function goes here % Detailed explanation goes here global map; global isvisited; global Anode; global fen; isvisited(1,f)=1; for i=1:size(map,1) dis=distance(Anode(f,2),Anode(f,3),Anode(i,2),Anode(i,3)); if(map(f,i)~=-1 && isvisited(1,i)==0) if( morelen>0)
if(morelen>=dis)
plot([Anode(f,2),Anode(i,2)],[Anode(f,3),Anode(i,3)],['-',cor]);
fun(i,morelen-dis);

else
[x,y]=fendian(Anode(f,2),Anode(f,3),Anode(i,2),Anode(i,3),morelen);
fen=[fen;i,Anode(i,2),Anode(i,3)];
plot([Anode(f,2),x],[Anode(f,3),y],['-',cor]);
% plot([x,Anode(i,2)],[y,Anode(i,3)],'-r');

end
else
% plot([Anode(f,2),Anode(i,2)],[Anode(f,3),Anode(i,3)],'-r');

end
end
end
isvisited(1,f)=0;
end

function [x,y]=fendian(x1,y1,x2,y2,len)
dis=distance(x1,y1,x2,y2);
x=x1+(x2-x1)*(len/dis);
y=y1+(y2-y1)*(len/dis);
end

附录七
nodedata = xlsread('2011b.xls','全市交通路口的路线','A2:B929')
distancedata = xlsread('2011b.xls','全市交通路口节点数据','A2:C583');
police = xlsread('2011b.xls','全市交巡警平台','B2:B81');
Anode=distancedata;
global map;
global fen;
map=0;
fen=[];
map=-ones(size(distancedata,1))+eye(size(distancedata,1));
for i=1:size(nodedata,1)
map(nodedata(i,1),nodedata(i,2))=1;
map(nodedata(i,2),nodedata(i,1))=1;
end
hold on
for i=1:size(police,1)
plot(distancedata(police(i,1),2),distancedata(police(i,1),3),'or');
end

for i=1:size(distancedata,1)
plot(distancedata(i,2),distancedata(i,3),'.b');
end

for i=1:size(nodedata,1)
plot([distancedata(nodedata(i,1),2),distancedata(nodedata(i,2),2)],[distancedata(nodedata(i,1),3),distancedata(nodedata(i,2),3)],':');
end
plot(326,355,'*r');
text(326,365,'P');

for i=1:20
isvisited(1:582)=0;
fun(i,30);
end

for i=93:100
isvisited(1:582)=0;
fun(i,30);
end

for i=166:182
isvisited(1:582)=0;
fun(i,30);
end

for i=320:328
isvisited(1:582)=0;
fun(i,30);
end

for i=372:386
isvisited(1:582)=0;
fun(i,30);
end

for i=475:485
isvisited(1:582)=0;
fun(i,30);
end
hold off

附录八
%二分求+匈牙利求出全市封锁所需要最短时间与方案的程序
%y是最大值,road(i)表示第i个警务室分配的路口
function [y,road]=getmax2()
clc
global rightpoint;
global graph;
global police;
rsize=size(rightpoint,1);
maxn=0;
for i=1:size(police,1)
for j=1:rsize
maxn=max(maxn,graph(police(i),rightpoint(j)));
end
end
beg=0;
while(beg
#include
#include
#include
#include
#include
using namespace std;

#define maxN 610
#define MAXX 0x0ffffffff
int st[maxN],en[maxN];
double map[maxN][maxN];
bool vist[maxN],f[maxN];
int pre[maxN],ke[maxN],d[maxN][maxN];

//最小费用最大流求最优匹配
#define maxM 40100
#define inf 0x7fffffff
struct point{
int v,next,f;
double w;
}po[maxM];
int num,head[maxN],vis[maxN];
double dis[maxN],fa[maxN];
void add(int u,int v,int f,double cow)
{
po[num].v=v;po[num].f=f;po[num].w=cow;
po[num].next=head[u];head[u]=num++;
po[num].v=u;po[num].f=0;po[num].w=-cow;
po[num].next=head[v];head[v]=num++;
}
bool spfa(int s,int n)
{
for(int i=0;i<=n+1;i++) dis[i]=inf; memset(pre,-1,sizeof(pre)); memset(vis,0,sizeof(vis)); queueq;
q.push(0);
dis[0]=0;vis[0]=1;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
for(int i=head[u];i!=-1;i=po[i].next){
int v=po[i].v;
if(po[i].f!=0&&dis[v]>dis[u]+po[i].w){
dis[v]=dis[u]+po[i].w;
pre[v]=i;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
if(pre[n]==-1)return false;
return true;
}
double max_low(int s,int t)
{
double ans=0;
while(spfa(s,t)){
ans+=dis[t];
int k=pre[t];
while(k!=-1){
po[k].f--;
po[k^1].f++;//cout< 0){
cnt+=map[u][po[j].v];
cout<

我猜你可能也喜欢:

7 Comments - Leave a comment
  1. 楼主,请问一下怎么处理第一问中表格的数据呀,比如1和15节点形成一条路,那么怎么才能求这条路的路程呢?一条路的路程好求,只是不知道有那么多条路,而且在两个表格中的排列顺序也不一样,所以不知道怎么求,要是知道了如何处理数据,后面的都好说,就要交作业了,还行楼主教我,非常谢谢!!!

  2. 小坏蛋说道:

    之前的问题我懂了,可是我不明白为什么要用92*92的矩阵,这需要多大的工作量啊

    • 三江小渡说道:

      很久前的程序了,大致看了一下,是用来进行二分图最大权边最小的计算这个矩阵不算大

      • 小坏蛋说道:

        不知道是不是没看懂你的程序,求两个节点之间的距离应该考虑到路线的选择吧?也就是不可以直接用两点的直线距离来表示,如何按照实际情况用程序求出路口到交巡警平台之间的路程是我最大的困扰。。。。
        ps:用耗子和小坏蛋留言并非故意,请见谅

        • 三江小渡说道:

          我记得就是按给的数据构造矩阵,使用的是floyd算法 是考虑到权边的,求的就是最短路线,已经让程序作出了最优选择了,建议你了解一下程序里边提到的各种算法,就清楚了

          • 小坏蛋说道:

            果然是高手,一语点醒梦中人啊! 很惭愧竟然对floyd算法一点不了解,百度后重新看您的文章才发现自己的问题出在哪,谢谢了,以后会经常来“拜师学艺”的,别嫌麻烦啊:)

  3. 小坏蛋说道:

    matrix(num92,num92):c;

    c=@file(‘C:\Users\iphxer\Documents\MATLAB\g.txt’);
    求楼主解释两个问题 :1 导入数据@file()括号内不需要有引号吧; 2 g.txt里的数据该是什么样的格式呢?为什么我总是在这个导入数据上出错

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期一, 2017 年 09 月 25 日