今日白嫖 1/∞ 🤣
http://acm.cugb.edu.cn/problem_show.php?pid=2331
http://acm.cugb.edu.cn/problem_show.php?pid=1262
#include <iostream> #include <string> #include <algorithm> #include <cmath> #include <cstring> #include <map> #include <vector> #include <queue> #define INF 0x3f3f3f3f using namespace std; //--------------------------------- //贪心法: //贪心法求解背包问题 /* 7 15 2 10 3 5 5 15 7 7 1 6 4 18 1 3 */ struct thing{ int id=0; int w=0; int p=0; double wp=0; int useWeight=0; }; bool cmp(thing &t1, thing &t2){ return t1.wp>t2.wp; } bool cmp_id(thing &t1, thing &t2){ return t1.id<t2.id; } void pro_1(){ int n=0, size=0; scanf("%d%d",&n, &size); vector<thing> things(n); for(int i=0;i<n;++i){ things.at (i).id=i; scanf("%d%d",&things.at (i).w,&things.at (i).p); things.at (i).wp=things.at (i).p*1.0/things.at (i).w; } sort(things.begin (), things.end (), cmp); // for(auto &temp: things){ // printf("%d %d %lf\n",temp.w, temp.p, temp.wp); // } int sizeNow=0; double price=0; // vector<int> weight; for(int i=0;i<n; ++i){ if(sizeNow+things.at (i).w<=size){ sizeNow+=things.at (i).w; things.at (i).useWeight=things.at (i).w; price+=things.at (i).p; }else{ things.at (i).useWeight=size-sizeNow; price+=(size-sizeNow)*things.at (i).wp; break; } } sort(things.begin (), things.end (), cmp_id ); printf("%.2lf\n",price); printf("%d",things.at (0).useWeight); for(int i=1;i<n;++i){ printf(" %d",things.at (i).useWeight); } return ; } int main() { pro_1 (); return 0; }http://acm.cugb.edu.cn/problem_show.php?pid=1036
这里用的Kruscal算法
#include <iostream> #include <string> #include <algorithm> #include <cmath> #include <cstring> #include <map> #include <vector> #include <queue> #define INF 0x3f3f3f3f using namespace std; const int MAX=105; int graph[MAX][MAX]={0}; struct edge{ int p1; int p2; int length=0; }; bool cmp(edge &e1, edge &e2 ){ return e1.length<e2.length; } void initialize(vector<int> &p){ int n=p.size (); for(int i=0;i<n;++i){ p.at (i)=i; } return ; } int find(int p, vector<int> &father){ if(father.at (p)==p){ return p; }else{ return father.at (p)=find(father.at (p),father); } } int unionPoints(int p1, int p2, vector<int> &father){ int father1=find(p1,father); int father2=find(p2,father); father.at (father2)=father1; return father1; } void pro_2(){ int n=0; scanf("%d",&n); vector<edge> e; // for(int i=1;i<3;++i){ // for(int j=0;j<80;++j){ // printf("%d ",count++); // } // putchar('\n'); // } int edgeCount=0; for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ e.push_back (edge()); e.at (edgeCount).p1=i; e.at (edgeCount).p2=j; scanf("%d",&e.at (edgeCount++).length); } } // for(int i=0;i<n;++i){ // for(int j=0;j<n;++j){ // printf("%d ",graph[i][j]); // } // putchar('\n'); // } // for(auto &temp:e){ // printf("%d--->%d=%d\n",temp.p1, temp.p2, temp.length); // } sort(e.begin (), e.end (), cmp); vector<int> father(n); initialize (father); int len=0; for(int i=0, count=0;i<edgeCount && count<n;++i){ edge &nowEdge=e.at (i); if(find(nowEdge.p1, father)!=find(nowEdge.p2, father)){ unionPoints (nowEdge.p1, nowEdge.p2, father); len+=nowEdge.length; ++count; } } printf("%d",len); return ; } int main() { pro_2 (); return 0; }http://acm.cugb.edu.cn/problem_show.php?pid=1191
#include <iostream> #include <string> #include <algorithm> #include <cmath> #include <cstring> #include <map> #include <vector> #include <queue> #define INF 0x3f3f3f3f using namespace std; const int MAX=105; struct edge{ int p1; int p2; int length=0; }; bool cmp(edge &e1, edge &e2 ){ return e1.length<e2.length; } void initialize(vector<int> &p){ int n=p.size (); for(int i=0;i<n;++i){ p.at (i)=i; } return ; } int find(int p, vector<int> &father){ if(father.at (p)==p){ return p; }else{ return father.at (p)=find(father.at (p),father); } } int unionPoints(int p1, int p2, vector<int> &father){ int father1=find(p1,father); int father2=find(p2,father); father.at (father2)=father1; return father1; } vector<edge> e; void pro_3(){ int testNum=0; scanf("%d",&testNum); while(testNum--){ int n,m,k; scanf("%d%d%d",&n,&m,&k); const int MAX_P=505; vector<int> father(MAX_P); initialize (father); for(int i=0;i<m;++i){ e.push_back (edge()); scanf("%d%d%d", &e.at (i).p1, &e.at (i).p2,&e.at (i).length); } sort(e.begin (), e.end (), cmp ); int tempPoint[MAX_P]={0}; for(int i=0;i<k;++i){ int pointN=0; scanf("%d",&pointN); for(int j=0;j<pointN;++j){ scanf("%d",&tempPoint[j]); } for(int j=1;j<pointN;++j){ unionPoints (tempPoint[j-1],tempPoint[j],father); } } int price=0; for(int i=0, count=0;i<m && count<n; ++i){ edge &nowEdge=e.at (i); if(find(nowEdge.p1, father)!=find(nowEdge.p2, father)){ unionPoints (nowEdge.p1, nowEdge.p2, father); price+=nowEdge.length; } } //检测所有城市是否都为同一个集合 int father1=find(1, father); bool flag=true; for(int i=2;i<=n;++i){ if(father1!=find(i,father)){ flag=false; break; } } //输出 if(flag){ printf("%d\n",price); }else{ printf("-1\n"); } } return ; } int main() { pro_3 (); return 0; }http://acm.cugb.edu.cn/problem_show.php?pid=1077
#include <iostream> #include <string> #include <algorithm> #include <cmath> #include <cstring> #include <map> #include <vector> #include <queue> #include <stack> #define INF 0x3f3f3f3f using namespace std; /* 6 4 1 2 1 1 3 4 1 4 5 2 3 6 3 4 3 2 4 2 */ const int MAX=1005; int graph[MAX][MAX]={0}; int dis[MAX]={0}; bool visited[MAX]={0}; void pro_4(){ int t, n; scanf("%d%d",&t, &n); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ graph[i][j]=INF; } } for(int i=0;i<=n;++i){ graph[i][i]=0; } for(int i=1;i<=n;++i){ dis[i]=INF; } dis[n]=0; int p1,p2,l; for(int i=0;i<t;++i){ scanf("%d%d%d",&p1, &p2, &l); graph[p1][p2]=l; graph[p2][p1]=l; } queue<int> p; p.push (n); int nodeNow=n; while(!p.empty ()){ nodeNow=p.front (); p.pop (); for(int i=1;i<=n;++i){ if(graph[nodeNow][i]!=INF){ dis[i]=min(dis[i],dis[nodeNow]+graph[nodeNow][i]); } if(!visited[i]){ p.push (i); } } visited[nodeNow]=true; } // for(int i=1;i<=n;++i){ // printf("%d ", dis[i]); // } printf("%d",dis[1]); return ; } int main() { pro_4 (); return 0; }