中天建设集团有限公司总网站,wordpress移动导航,哈尔滨市工程建设监理有限公司,成都关键词战争
题目描述
X国和Y国是死对头#xff0c;X国有N个炮台, Y国有M个基地和K个发电站#xff0c;炮台、基地、发电站所在的位置的坐标都是整数。Y国的每个发电站能对距离其L以内#xff08;包括L#xff09;的基地供电。X国的每个炮台都可以发射无限次#xff0c;每次发射…战争
题目描述
X国和Y国是死对头X国有N个炮台, Y国有M个基地和K个发电站炮台、基地、发电站所在的位置的坐标都是整数。Y国的每个发电站能对距离其L以内包括L的基地供电。X国的每个炮台都可以发射无限次每次发射可以击毁一个基地或者一个发电站消耗的能量为两者距离的平方这里的距离是欧几里德距离。X国决定要摧毁Y国的所有基地我们说Y国的某个基地被摧毁的条件是基地本身被直接摧毁或者对其供电的所有发电站被击。 问X国摧毁Y国所有基地需要消耗的总能量最小是多少。 提示点X1,Y1和点X2,Y2的欧几里德距离是 dis sqrt( (X2-X1)* (X2-X1) (Y2-Y1)* (Y2-Y1)).
输入格式 1894.in
第一行四个整数N、M、K、L。1 N、M、K 50. 1L2000. 第二行N个整数第i个整数表示第i个炮台的横坐标。 第三行N个整数第i个整数表示第i个炮台的纵坐标。 第四行M个整数第i个整数表示第i个基地的横坐标。 第五行M个整数第i个整数表示第i个基地的纵坐标。 第六行K个整数第i个整数表示第i个发电站的横坐标。 第七行K个整数第i个整数表示第i个发电站的纵坐标。 所有的坐标的范围[-500500]。所有的炮台、基地、发电站不会重复。 数据保证每个基地至少有一个发电站为其供电。
输出格式 1894.out
问X国摧毁Y国所有基地需要消耗的总能量最小是多少。 题目中有很多限制。需要一一去除才能明朗起来。 首先销毁每个发电站、基地的能量值需要进行预处理即所有大炮打它消耗能量中的最小值。 再者对题意进行分析我们可以打发电站也可以打基地。其中每个发电站可能对应许多个基地。如果基地的所有发电站都被销毁则基地也被销毁。 这就是个最小割问题。将其转化成图就变成这个样子可以割发电站也可以割基地且要构造使得从s能到t为非法的。因此可以如下构图 1建一个源点S连接所有发电站权值为销毁它的能量值。 2) 从所有发电站出发连接其能供电的基地权值为INF。 3从基地出发连接汇点T权值为销毁它的能量值。 根据最大流最小割定理直接在原图中跑一遍最大流即为答案。 代码如下 #include#include#include#include#includeusing namespace std; const int MAXN55,MAXE100005,INF1e75,MAXNO1005; int head[MAXNO],v[MAXNO],dpl[MAXN],dst[MAXN]; int n,m,k,l,s,t,cur-1; long long ans0; //1894.cpp struct wyy { int x,y; }cannon[MAXN],place[MAXN],station[MAXN]; struct e { int to,next,va; }edge[MAXE]; void add(int from,int to,int va) { edge[cur].toto; edge[cur].nexthead[from]; edge[cur].vava; head[from]cur; } void Read() { //ͼ: ·¢µçÕ¾ »ùµØ cinnmkl;//nΪÅŲ́£¬mΪ»ùµØ£¬kΪ·¢µçÕ¾£¬lΪ·¢µç¾àÀ루Ðèƽ·½£© s0; tkm1; for(int i1;in;i) cincannon[i].x;//ÅÚ for(int i1;in;i) cincannon[i].y; for(int i1;im;i) cinplace[i].x; for(int i1;im;i) cinplace[i].y; for(int i1;ik;i) cinstation[i].x; for(int i1;ik;i) cinstation[i].y; memset(head,-1,sizeof(head)); } void First_prepare() { //±éÀúÿ¸ö»ùµØ£¬¿´ÅŲ́µ½ËüÄÜÁ¿µÄ×îСֵ int xdiff,ydiff,dis; for(int i1;im;i)//»ùµØ£¬place { disINF; for(int j1;jn;j)//ÅŲ́£¬cannon { xdiffplace[i].x-cannon[j].x; ydiffplace[i].y-cannon[j].y; dismin(dis,xdiff*xdiffydiff*ydiff); } dpl[i]dis; //ansdpl[i]; } //±éÀúÿ¸ö·¢ÉäÕ¾£¬¿´ÅŲ́µ½ËüÄÜÁ¿×îСֵ for(int i1;ik;i)//·¢ÉäÕ¾£¬station { disINF; for(int j1;jn;j)//ÅŲ́£¬cannon { xdiffstation[i].x-cannon[j].x; ydiffstation[i].y-cannon[j].y; dismin(dis,xdiff*xdiffydiff*ydiff); } dst[i]dis; } } void Make_picture() { int xdiff,ydiff,dis; for(int i1;ik;i)//·¢ÉäÕ¾ s-·¢µçÕ¾ { add(s,i,dst[i]); add(i,s,0); } for(int i1;ik;i)//·¢µçÕ¾Á¬ { for(int j1;jm;j) { xdiffstation[i].x-place[j].x; ydiffstation[i].y-place[j].y; disxdiff*xdiffydiff*ydiff; if(disl*l) { add(i,kj,INF); add(kj,i,0); } } } //»ùµØµ½t for(int i1;im;i) { add(ki,t,dpl[i]); add(t,ki,0); } } int dfs(int cur,int mina) { if(curt) return mina; v[cur]1; int hhead[cur]; while(h!-1) { int toedge[h].to,vaedge[h].va; if(v[to]0va!0) { int resdfs(to,min(mina,va)); if(res!0) { edge[h].va-res; edge[h^1].vares; return res; } } hedge[h].next; } return 0; } void Ed() { while(1) { memset(v,0,sizeof(v)); int resdfs(s,INF); if(res0) break; ansres; } } int main() { ios::sync_with_stdio(false); Read(); First_prepare(); Make_picture(); Ed(); cout
