代码仓库

21

代码仓库

最小生成树（prim），hdu1102

#include #include #include usingnamespace std; constint N=107; int n,g[N][N];

int prim(){

int minw[N];//MinWeight bool used[N];

memset(used,0,sizeof(used)); memset(minw,0x7f,sizeof(minw)); minw[1]=0; int sum=0; while(1){ int v=-1;

for(int i=1;i<=n;i++){

if(!used[i]&&(v==-1||minw[i]

if(v==-1)break; used[v]=1; sum+=minw[v]; for(int i=0;i<=n;i++){

minw[i]=min(minw[i],g[v][i]); } }

return sum; }

22

代码仓库

int main(){ for(;scanf(\,&n)==1;){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)scanf(\,&g[i][j]); int x,y,q; scanf(\,&q); for(;q--;){ scanf(\,&x,&y); g[x][y]=g[y][x]=0; } printf(\,prim()); } return0; }

次小生成树hdu4081

//hdu4081 次小生成树 #include #include #include #include usingnamespace std; constint N=1007; int n; double g[N][N],maxw[N][N]; bool used[N][N]; struct City{ int x,y,w;//w=population City():x(0),y(0),w(0){} City(int _x,int _y,int _w):x(_x),y(_y),w(_w){} 23

代码仓库

}citys[N];

double dist(City a,City b){

return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }

double prim(){ int from[N]; bool vis[N]; double minw[N];

for(int i=1;i<=n;i++){ minw[i]=g[1][i]; from[i]=1; }

memset(used,0,sizeof(used)); memset(maxw,0,sizeof(maxw)); memset(vis,0,sizeof(vis)); vis[1]=1; minw[1]=0; double sum=0; while(1){ int v=-1;

for(int i=1;i<=n;i++)if(!vis[i]){ if(v==-1||minw[i]

if(v==-1)break;

used[v][from[v]]=used[from[v]][v]=1; vis[v]=1; sum+=minw[v]; for(int i=1;i<=n;i++){

if(!vis[i]&&g[v][i]

if(vis[i]&&i!=v){

maxw[i][v]=maxw[v][i]=max(maxw[i][from[v]],minw[v]); } } }

return sum; }

int main(){

24

代码仓库

//freopen(\int T;scanf(\,&T); for(;T--;){

scanf(\,&n);int x,y,z; for(int i=1;i<=n;i++){

scanf(\,&x,&y,&z); citys[i]=City(x,y,z); }

for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) g[i][j]=dist(citys[i],citys[j]);

double sum=prim(),ans=-1; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){

if(used[i][j])ans=max(ans,(citys[i].w+citys[j].w)/(sum-g[i][j])); else ans=max(ans,(citys[i].w+citys[j].w)/(sum-maxw[i][j])); } }

printf(\,ans); }

return0; }

最大流（Dinic）

#include #include #include #include #include #include usingnamespace std; typedeflonglong LL; constint INF=0x3f3f3f3f; constint N =23<<1; 25

代码仓库

int n,m,a[N],b[N],ans[N][N];

struct gragh{ struct Edge{

int from,to,cap,flow;

Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} };

int s,t;//0=s,1~nАn+1~n+mPn+m+1=t vectoredges; vectorG[N];//gragh bool vis[N];//use when bfs

int d[N],cur[N];//dist,now edge,use in dfs inlinevoid AddEdge(int from,int to,int cap){ edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); int top=edges.size();

G[from].push_back(top-2); G[ to ].push_back(top-1); }

inlinebool BFS(){

memset(vis,0,sizeof(vis)); queueQ;

Q.push(s);d[s]=0;vis[s]=1; while(!Q.empty()){ int x=Q.front();Q.pop();

for(int i=0;i

return vis[t]; }

inlineint DFS(constint& x,int a){ //printf(\if(x==t||a==0){return a;} int flow =0, f;

for(int& i=cur[x];i