Analiza programów

17.06.2009

Prestiż

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int DEBUG = 0;  //REV: być może fajnie by było mieć makro  #define dprintf if(DEBUG)printf
const int SIZE = 100001;     // liczba wie   //REV: co wie?:)
 
struct wie{
       vector<int> s;
       int waga;
       int pre;
       int low;
       int nr;   // nr spojnej skladowej
};
 
wie t[SIZE];
int n,m;
stack<int> s;
int cykle[SIZE];	// rozmiary poszcz. silnie spojnych skladowych (cykli)
bool nieRoot[SIZE];
vector<int> wybor;
 
int sklI = 0;	// liczba silnie spojnych skladowych
int dfsI = 1;
int dfs(int u)//REV: wcięcia się coœ potentegowały
{
    if(DEBUG) printf("dfs(%d) ", u);
    int preSize = s.size();
    s.push(u);
 
    t[u].pre = dfsI++;
    t[u].low = t[u].pre;
 
    for(int i=0; i<t[u].s.size(); i++){
            int nr = t[u].s[i];
            if(t[nr].nr == 0){
               if(t[nr].pre == 0) dfs(nr);
               t[u].low = min(t[u].low, t[nr].low);
            }
    }
 
    // jesli wyzej ode mnie jest juz inna spojna skladowa
    // to odcinam wszystko nizej razem ze mna do jednej silnie spojnej skladowej
    if(t[u].low == t[u].pre)
	{
                int rozm = s.size() - preSize;
                if(DEBUG) printf("Odc od wie %d (rozm. %d == %d - %d): ", u, rozm, s.size(), preSize);
 
                int sklNr = ++sklI;
 
                while(s.top() != u){
                   t[s.top()].nr = sklNr;
                   cykle[sklNr] = max(cykle[sklNr], t[s.top()].waga);
                   if(DEBUG) printf("%d ", s.top());
                   s.pop();
                }
 
                t[s.top()].nr = sklNr;
                cykle[sklNr] = max(cykle[sklNr], t[s.top()].waga);
                if(DEBUG) printf("%d ", s.top());
                s.pop();
 
                if(DEBUG) printf("\n");
    }
 
    if(DEBUG) printf("low(%d) == %d\n", u, t[u].low);
    //REV: ta funkcja miała zwracać integera
}
 
void read(){
	scanf("%d%d", &n,&m);
 
	for(int i=1; i<=n; i++) scanf("%d", &(t[i].waga));
 
    int a,b;
    for(int i=0; i<m; i++){
            scanf("%d%d", &a, &b);
            t[a].s.push_back(b);
    }
}
 
void findRoots(){
     for(int u=1; u<=n; u++){
             int cykl = t[u].nr;
             for(int j=0; j<t[u].s.size(); j++){
                     int nr = t[u].s[j];
                     if(t[nr].nr != cykl) nieRoot[t[nr].nr] = true;
             }
     }
}
 
void calc(){
     int ile=0, sum=0;
     if(DEBUG) printf("Dodaje wierzcholki do sredniej:\n");
     if(DEBUG) printf("Korzenie(cykle):\n");
 
     for(int i=1; i<=sklI; i++){
             if(!nieRoot[i]){ // cykl to jeden z korzeni
               if(DEBUG) printf("%d - waga: %d\n", i, cykle[i]);
               ile++;
               sum += cykle[i]; // predzej czy pozniej trzeba go udowodnić
             }
             else wybor.push_back(cykle[i]);
     }
 
     sort(&(wybor[0]), &(wybor[wybor.size()]));
     if(DEBUG) printf("Reszta:\n");
 
     for(int i=wybor.size()-1; i>=0; i--){
             if(sum*(ile+1) < (sum+wybor[i])*(ile)){
               if(DEBUG) printf("waga %d\n", wybor[i]);
               ile++;
               sum += wybor[i];
             }
             else break;
     }
 
     if(DEBUG) printf("Ile: %d, suma: %d\n", ile, sum);
     printf("%.5f\n", (float)sum / (float)ile);
}
 
int main()
{
    for(int i=0; i<SIZE; i++) cykle[i] = -1000000;
    read();
 
	// Znajdujemy silnie spójne składowe (cykle)
    for(int i=1; i<=n; i++) if(t[i].pre == 0) dfs(i);
 
    if(DEBUG) {
		printf("Oto nr-y silnie spojnych skladowych:\n");
		for(int i=1; i<=n; i++) printf("%d nr: %d\n", i, t[i].nr);
 
		printf("Oto cykle. -===========-:\n");
		for(int i=1; i<=sklI; i++) printf("nr: %d, waga: %d\n", i, cykle[i]);
	}
 
	findRoots();
 
	calc();
 
//  int nic;scanf("%d", &nic);
  return 0;
}
 
 

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com