Λύσεις Β φάσης 29ου ΠΔΠ
Λύσεις Β φάσης 29ου ΠΔΠ
Εδώ μπορείτε να αναρτήσετε και να συζητήσετε τις λύσεις σας για τα προβλήματα της Β φάσης.
Καλή επιτυχία και καλή συνέχεια σε όλους
Καλή επιτυχία και καλή συνέχεια σε όλους
Re: Λύσεις Β φάσης 29ου ΠΔΠ
Αλγόριθμος Prim με priority_queue
Πολυπλοκότητα O(nlogn)
Πολυπλοκότητα O(nlogn)
Κώδικας: Επιλογή όλων
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <fstream>
using namespace std;
class Graph{
int V;
public:
vector<vector<pair<int,int> > > adj;
Graph(int a);
void addEdge(int u, int v, int w);
};
Graph::Graph (int a){
V=a;
adj.resize(V);
}
void Graph::addEdge(int u ,int v ,int w){
adj[u].push_back(make_pair(v,w));
adj[v].push_back(make_pair(u,w));
}
int main() {
ifstream fin ;
ofstream fout;
fin.open("uflights.in");
fout.open("uflights.out");
int n,m;
fin>> n >> m;
Graph g(n);
for(int ii=0;ii<m;ii++){
int u,v,w;
fin>>u>>v>>w;
u--;
v--;
g.addEdge(u,v,w);
}
priority_queue< pair<int,int>, vector <pair<int,int> > , greater<pair<int , int > > > priority_q;
vector<int> dist (n,INT_MAX);
vector<bool> used (n,false);
priority_q.push(make_pair(0,0));
dist[0]=0;
long long int answer=0;
while(priority_q.empty()==false){
int u=priority_q.top().second;
if(used[u]==false)answer+=priority_q.top().first;
priority_q.pop();
used[u]=true;
for(int ii=0;ii<g.adj[u].size();ii++){
int v=g.adj[u][ii].first;
int w=g.adj[u][ii].second;
if(used[v]==false && dist[v]>w){
dist[v]=w;
priority_q.push(make_pair(w,v));
}
}
}
fout << answer << endl;
return 0;
}
Re: Λύσεις Β φάσης 29ου ΠΔΠ
Κώδικας: Επιλογή όλων
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <list>
#define p2Int pair<int,int>
#define pIntP2Int pair<int,p2Int>
#define Nmax 1000001
using namespace std;
int edges , N ;
bool counter[Nmax] = {false};
typedef struct node {
int x , y ;
int weight ;
}node;
list<node> p ;
bool lessthan(const node& a,const node& b){
return a.weight < b.weight ;
}
int mst(void){
int minc = 0;
while(!p.empty()){
for(list<node>::iterator i = p.begin() ; i !=p.end() ; i++){
if(counter[i->x] && counter[i->y]){
p.erase(i);
break ;
}else if(!counter[i->x] && !counter[i->y]){
continue ;
}else{
counter[i->x] = counter[i->y] = true ;
minc += i->weight ;
p.erase(i);
break;
}
}
}
return minc ;
}
int main()
{
printf("edges: ");
scanf("%d",&edges);
printf("nodes: ");
scanf("%d",&N);
int x,y,weight ;
printf("write me the nodes syntax : ( weight(cost) , node a , node b )-:\n");
for(int i = 0 ; i < N ; i++){
scanf("%d %d %d",&x,&y,&weight);
node temp ;
temp.weight = weight ;
temp.x = x ;
temp.y = y ;
p.push_back(temp);
}
p.sort(lessthan);
printf("minimum cost is : %d\n",mst());
return 0 ;
}
Re: Λύσεις Β φάσης 29ου ΠΔΠ
για το γυμνάσιο:
Κώδικας: Επιλογή όλων
#include <cstdio>
int N,K,A[1000001]={0},
C[100001]={0},minC=2000000;
using namespace std;
int main(){
FILE *in=fopen("colors.in","r"),*out=fopen("colors.out","w");
fscanf(in,"%d%d",&N,&K);
for(int R=1,L=1,nC=0;R<=N;R++){
fscanf(in,"%d",A+R);
if(C[A[R]]==0)
nC++;
C[A[R]] = R;
if(nC == K){//are we colorful?
while(L<R && C[A[L]]>L)
L++;
if(R-L+1 < minC)
minC = R-L+1;
}
}
fprintf(out,"%d\n",minC<=N?minC:0);
return 0;
}
Τελευταία επεξεργασία από το μέλος Κηπουρίδης την Πέμ Μαρ 23, 2017 11:29 am, έχει επεξεργασθεί 1 φορά συνολικά.
Λόγος: Αίτημα του χρήστη qsort.
Λόγος: Αίτημα του χρήστη qsort.
-
- Δημοσιεύσεις: 2
- Εγγραφή: Σάβ Δεκ 31, 2016 5:50 pm
Re: Λύσεις Β φάσης 29ου ΠΔΠ
Για το Λύκειο (αλγοριθμος Kruskal):
Για το Γυμνάσιο:
BTW τα αποτελέσματα ποτε περίπου θα βγουν?
Κώδικας: Επιλογή όλων
#include <bits/stdc++.h>
#define fastIo ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
using namespace std;
//#define LOCAL
#ifdef LOCAL
#define DEBUG(x) do { cout << #x << ": " << x << '\n'; } while (0)
#else
#define DEBUG(x)
#endif
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
inline int read(){
register int c = getc_unlocked(stdin);
int x = 0;
for(; (c < 48 || c > 57); c = getc_unlocked(stdin));
for(; (c > 47 && c < 58); c = getc_unlocked(stdin)){ x = (x << 1) + (x << 3) + c - 48; }
return x;
}
struct Edge{
int from, to;
int weight;
Edge(int from, int to, int weight)
: from(from), to(to), weight(weight) {}
};
bool cmp(const Edge& a, const Edge& b){
return a.weight < b.weight;
}
int id[100005], Rank[100005];
void Init(int n){
for(int i = 0; i < n; i++){
id[i] = i;
Rank[i] = 0;
}
}
int Find(int u){
while(u != id[u]){
id[u] = id[id[u]];
u = id[u];
}
return u;
}
void Union(int u, int v){
int i = Find(u), j = Find(v);
if(Rank[i] < Rank[j]) id[i] = j;
else if(Rank[i] > Rank[j]) id[j] = i;
else{
id[i] = j;
Rank[j]++;
}
}
vector<Edge> edges;
int main(){
freopen("uflights.in", "r", stdin);
freopen("uflights.out", "w", stdout);
int n = read();
int m = read();
int a, b, w;
for(int i = 0; i < m; i++){
a = read(), b = read(), w = read();
a--, b--;
edges.pb(Edge(a, b, w));
}
sort(all(edges), cmp);
Init(n);
int ans = 0;
for(int i = 0; i < edges.sz(); i++){
int u = edges[i].from, v = edges[i].to;
if(Find(u) != Find(v)){
Union(u, v);
ans += edges[i].weight;
}
}
printf("%d\n", ans);
return 0;
}
Κώδικας: Επιλογή όλων
#include <bits/stdc++.h>
#define fastIo ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
using namespace std;
//#define LOCAL
#ifdef LOCAL
#define DEBUG(x) do { cout << #x << ": " << x << '\n'; } while (0)
#else
#define DEBUG(x)
#endif
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
int col[1000005];
map<int, int> freq;
int main(){
freopen("colors.in", "r", stdin);
freopen("colors.out", "w", stdout);
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> col[i];
int l = 0, count = 0, ans = 10000009;
for(int i = 0; i < n; i++){
if(freq[col[i]] == 0) count++;
freq[col[i]]++;
if(count == k){ // Eαν στο διαστημα [l, i] εχουμε ολα τα χρωματα
while(freq[col[l]] > 1) freq[col[l]]--, l++; // Αυξανουμε το l οσο η συνθηκη διατηρειται
ans = min(ans, i - l + 1);
}
}
if(ans == 10000009) cout << "0\n";
else cout << ans << '\n';
return 0;
}
Re: Λύσεις Β φάσης 29ου ΠΔΠ
Βγήκαν τα αποτελέσματα! Πολλά συγχαρητήρια στους επιτυχόντες
- Κηπουρίδης
- Δημοσιεύσεις: 397
- Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm
Re: Λύσεις Β φάσης 29ου ΠΔΠ
Στο γυμνάσιο βλέπω έχετε βρει τη γραμμική λύση, συγχαρητήρια!
Σχετικά με το λύκειο, προσέξτε ότι κάνοντας Kruskal δε χρειάζεται να ταξινομήσετε κατά βάρος τις ακμές αφού το βάρος τους είναι πολύ μικρό (μέχρι 100). Αρκεί να κάνετε 100 πίνακες, έναν για κάθε διακριτό βάρος, και να βάλετε την κάθε ακμή στον κατάλληλο πίνακα.
Έτσι έχετε "ταξινομήσει" σε γραμμικό χρόνο, φεύγει λοιπόν το logN από την πολυπλοκότητα. Ο υπόλοιπος Kruskal τρέχει (στην πράξη) γραμμικά (στη θεωρία N*α(N) όπου α(Ν) είναι η inverse ackermann συνάρτηση, που για κάθε Ν που μπορείτε να φανταστείτε (πχ 2^(1.000.000.000.000) ) είναι μικρότερη του 5).
Θερμά συγχαρητήρια σε όλους τους διαγωνιζόμενους!
Σχετικά με το λύκειο, προσέξτε ότι κάνοντας Kruskal δε χρειάζεται να ταξινομήσετε κατά βάρος τις ακμές αφού το βάρος τους είναι πολύ μικρό (μέχρι 100). Αρκεί να κάνετε 100 πίνακες, έναν για κάθε διακριτό βάρος, και να βάλετε την κάθε ακμή στον κατάλληλο πίνακα.
Έτσι έχετε "ταξινομήσει" σε γραμμικό χρόνο, φεύγει λοιπόν το logN από την πολυπλοκότητα. Ο υπόλοιπος Kruskal τρέχει (στην πράξη) γραμμικά (στη θεωρία N*α(N) όπου α(Ν) είναι η inverse ackermann συνάρτηση, που για κάθε Ν που μπορείτε να φανταστείτε (πχ 2^(1.000.000.000.000) ) είναι μικρότερη του 5).
Θερμά συγχαρητήρια σε όλους τους διαγωνιζόμενους!
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/