软件开发涵盖网站开发吗,有没有好的做海报的网站,如何加强省市级政门户网站建设,网站可信度必须做吗题目大意#xff1a;
有n个城市#xff0c;有一部分是A国的#xff0c;有一部分是B国的#xff08;小于A国的#xff09;#xff0c;A国每个城市都有一枚导弹#xff08;只有一枚#xff09;#xff0c;炸毁别的城市的时间是到这个城市的距离#xff0c;请问A国最快…题目大意
有n个城市有一部分是A国的有一部分是B国的小于A国的A国每个城市都有一枚导弹只有一枚炸毁别的城市的时间是到这个城市的距离请问A国最快要多久可以炸毁B国所有城市 解题思路
先用Floyed来求出最短路然后二分枚举答案再用匈牙利算法确认是否可以即可 代码
#includecstdio
#includeiostream
#includealgorithm
#includecstring
using namespace std;
int bg[105],head[105],a[105][105],b[105],c[105],w,sum,l,r,mid,n,m,nm;
bool pd[105];
struct rec
{int to,next;
}f[10005];//每一条路线
bool js(int xx)
{int l0;for (int ihead[xx];i;if[i].next)//连接此点的每一条线if (!pd[f[i].to])//可以抢{lbg[f[i].to];//之前是谁打的bg[f[i].to]xx;//代替pd[f[i].to]true;//不能抢了if ((!l)||(js(l))) return true;//之前没人或抢到了bg[f[i].to]l;//没法打这个城市就还给之前的}return false;//找不到可以打的
}
bool sj(int now)
{memset(head,0,sizeof(head));//清零memset(bg,0,sizeof(bg));//清零w0;//清零sum0;//清零for (int i1;in;i)for (int j1;jm;j)if (a[b[i]][c[j]]now)//判断是否少于当前的时间{f[w].toj;//下一个点f[w].nexthead[i];//下一条线head[i]w;//这个点的第一条线} for (int i1;in;i){memset(pd,false,sizeof(pd));//清零if (js(i)) sum;//判断是否能打到敌人}return summ;//判断是否打完
}
int main()
{scanf(%d,nm);for (int i1;inm;i)for (int j1;jnm;j)scanf(%d,a[i][j]);for (int k1;knm;k)for (int i1;inm;i)for (int j1;jnm;j)if ((i!j)(j!k)(k!i)(a[i][k]a[k][j]a[i][j]))a[i][j]a[i][k]a[k][j];//Floyedscanf(%d,n);for (int i1;in;i)scanf(%d,b[i]);scanf(%d,m);for (int i1;im;i)scanf(%d,c[i]);l1;r10000;while(lr){mid(lr)/2;//二分答案if (sj(mid)) rmid-1;else lmid1;}printf(%d,l);//输出return 0;
}
