网站建设的具体过程,深圳网站开发平台,wordpress 搜索 很慢,千图网cad免费素材图库正题 解题思路
一个东西可以拦截导弹#xff0c;每次只能打比上一次x,y,zx,y,zx,y,z都大的导弹。求一个最多可以拦截掉多少个导弹和至少要多少个才能拦截完。拦截导弹没有顺序要求。 解题思路
由于没有顺序要求所以我们可以直接定义一个比较#xff0c;然后第一问做法和导弹…正题 解题思路
一个东西可以拦截导弹每次只能打比上一次x,y,zx,y,zx,y,z都大的导弹。求一个最多可以拦截掉多少个导弹和至少要多少个才能拦截完。拦截导弹没有顺序要求。 解题思路
由于没有顺序要求所以我们可以直接定义一个比较然后第一问做法和导弹拦截差不多然后第二问最小路径覆盖。 codecodecode
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
struct line{int y,next;
}a[1101*1101];
struct node{int x,y,z;
}d[1101];
int link[1101],n,m,ls[1101],s,t,tot,num[1101],maxs,f[1101];
bool operator(node a,node b)
{return a.xb.xa.yb.ya.zb.z;};
bool cover[1101];
char c;
void addl(int x,int to)
{a[tot].nextls[x];a[tot].yto;ls[x]tot;return;
}
bool find(int x)
{int p0;for (int qls[x];q;qa[q].next){if (!cover[a[q].y]){plink[a[q].y];link[a[q].y]x;cover[a[q].y]true;if (!p || find(p)) return true;link[a[q].y]p;}}return false;
}
bool cmp(node a,node b)
{return a.xb.x;}
int main()
{freopen(missile.in,r,stdin);freopen(missile.out,w,stdout);scanf(%d,n);for(int i1;in;i)scanf(%d%d%d,d[i].x,d[i].y,d[i].z);sort(d1,d1n,cmp);for (int i1;in;i)//第一问{f[i]1;for (int j1;ji;j)if (d[j]d[i]) f[i]max(f[i],f[j]1);maxsmax(f[i],maxs);}printf(%d\n,maxs);for (int i1;in;i)//连边for (int j1;ji;j)if(d[j]d[i]) addl(i,j);for (int i1;in;i){memset(cover,false,sizeof(cover));if (find(i)) s;}printf(%d,n-s);
}
