Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
4.1 kB
0
Indexable
Never
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
 
 
class User {
    int mID;
    ArrayList<Integer> link;
    HashSet<String> fileSet;
     
    public User(int mID) {
        this.mID = mID;
        this.link = new ArrayList<Integer>();
        this.fileSet = new HashSet<String>();
    }
}
 
class Request {
    int userID;
    String fileName;
    ArrayList<Integer> path;
     
    public Request(int userID, String name) {
        this.userID = userID;
        this.path = new ArrayList<Integer>();
        this.fileName = name;
    }
}
 
class UserSolution
{
    int n;
    User[] user;
    Request[] request;
    int[][] bandwidth;
    HashMap<String, Integer> files;
     
    String toStr(char s[]) {
        int i;
        for(i = 0; s[i] != '\0'; i++);
        return new String(s, 0, i);
    }
     
 
    public void init(int N, int mUID1[], int mUID2[], int mBandwidth[])
    {
        n = N+1;
        user = new User[N+1];
        request = new Request[5001];
        bandwidth = new int[N+1][N+1];
        files = new HashMap<String, Integer>();
        for (int i = 1; i <= N; i++) {
            user[i] = new User(i);
        }
         
        for (int i = 0; i < N-1; i++) {
            bandwidth[mUID1[i]][mUID2[i]] = mBandwidth[i];
            bandwidth[mUID2[i]][mUID1[i]] = mBandwidth[i];
            user[mUID1[i]].link.add(mUID2[i]);
            user[mUID2[i]].link.add(mUID1[i]);
        }
    }
 
    public int share(int mUID, char mFilename[], int mFilesize)
    {
        String name = toStr(mFilename);
        files.put(name, mFilesize);
        user[mUID].fileSet.add(name);
        return user[mUID].fileSet.size();
    }
 
    public int request(int mUID, char mFilename[], int mTID)
    {
        String name = toStr(mFilename);
        Integer size = files.get(name);
        if (size == null) {
            return -1;
        }
        int ans = Integer.MAX_VALUE;
        Request req = new Request(mUID, name);
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(mUID);
        boolean[] visit = new boolean[n];
        int[] save = new int[n];
        boolean isFound = false;
         
        save[mUID] = -1;
        visit[mUID] = true;
         
        while (!queue.isEmpty()) {
            if (isFound) {
                break;
            }
            int s = queue.size();
            while (s > 0) {
                int u = queue.poll();
                for (int i = 0; i < user[u].link.size(); i++) {
                    int link = user[u].link.get(i);
                    if (bandwidth[link][u] >= size && !visit[link]) {
                        visit[link] = true;
                        queue.add(link);
                        save[link] = u;
                        if (user[link].fileSet.contains(name)) {
                            isFound = true;
                            ans = Math.min(ans, link);
                        }
                    }
                }
                s--;
            }
        }
        if (!isFound) {
            return -1;
        }
        int cur = ans;
        req.path.add(cur);
        while (save[cur] != -1) {
            int p = save[cur];
            req.path.add(p);
            bandwidth[cur][p] -= size;
            bandwidth[p][cur] -= size;
            cur = p;
        }
        request[mTID] = req;
        return ans;
    }
 
    public int complete(int mTID)
    {
        Request req = request[mTID];
        String name = req.fileName;
        int size = files.get(name);
        for (int i = 0; i < req.path.size()-1; i++) {
            int x = req.path.get(i);
            int y = req.path.get(i+1);
            user[y].fileSet.add(name);
            bandwidth[x][y] += size;
            bandwidth[y][x] += size;
        }
        return user[req.userID].fileSet.size();
    }
}
Leave a Comment